Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Ould-Khessal, Nadir
Doctor of Philosophy - PhD
University of British Columbia
Small devices used for agricultural, environmental, and industrial monitoring are typically built around embedded systems with limited computational power and memory. As these devices play a crucial role in data collection, there is a pressing need for optimizations to enhance on-device data processing, thereby reducing network transmissions, energy consumption, and data storage requirements. The most common type of data collected by these embedded devices is in the form of time series, encompassing environmental metrics like temperature and humidity, or operational data from sensors linked to machinery and electronics. Processing such time series datasets necessitates indexing both the sequentially increasing times tamps and the non-sequential data values. While database indexes such as the popular B-tree have been adapted to flash storage on servers and solid state drives, these optimizations typically demand hardware and memory resources beyond what is available on embedded devices. This work introduces both index types for memory-constrained embedded devices. For sequential indexing, the Sequential Binary Index for Time Series (SBITS) is introduced and evaluated against prior embedded indexes that used sorted files, trees, and hashing. The other contribution of this work is the development and experimental evaluation of flash-based indexes including multiple storage-specific variants of the B-tree such as the VMtree. Experimental results demonstrate that even the smallest devices can perform efficient B tree indexing, and there is a significant performance advantage for using storage-specific optimizations.
Indexing on Memory-ConstrainedEmbedded DevicesbyNadir Ould-KhessalM.Eng., University of BoumerdesDiploˆme de Post Graduation Specialise DPGS, Centre de Developpment desSyste`mes Energe´tiques -C.D.S.EA DISSERTATION SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)August 2024© Nadir Ould-Khessal, 2024The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a dissertation entitled:Indexing on Memory-Constrained Embedded Devicessubmitted by Nadir Ould-Khessal in partial fulfilment of the require-ments of the degree of Doctor of PhilosophyDr. Ramon Lawrence, Irving K. Barber Faculty of ScienceSupervisorDr. Yves Lucet, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Khalad Hasan, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Zheng Liu, School of EngineeringUniversity ExaminerDr. Ioanis Nikolaidis, University of AlbertaExternal ExamineriiAbstractSmall devices used for agricultural, environmental, and industrial mon-itoring are typically built around embedded systems with limited compu-tational power and memory. As these devices play a crucial role in datacollection, there is a pressing need for optimizations to enhance on-devicedata processing, thereby reducing network transmissions, energy consump-tion, and data storage requirements. The most common type of data col-lected by these embedded devices is in the form of time series, encompassingenvironmental metrics like temperature and humidity, or operational datafrom sensors linked to machinery and electronics. Processing such timeseries datasets necessitates indexing both the sequentially increasing times-tamps and the non-sequential data values. While database indexes such asthe popular B-tree have been adapted to flash storage on servers and solid-state drives, these optimizations typically demand hardware and memoryresources beyond what is available on embedded devices. This work in-troduces both index types for memory-constrained embedded devices. Forsequential indexing, the Sequential Binary Index for Time Series (SBITS) isintroduced and evaluated against prior embedded indexes that used sortedfiles, trees, and hashing. The other contribution of this work is the develop-ment and experimental evaluation of flash-based indexes including multiplestorage-specific variants of the B-tree such as the VMtree. Experimentalresults demonstrate that even the smallest devices can perform efficient B-tree indexing, and there is a significant performance advantage for usingstorage-specific optimizations.iiiLay SummaryThis dissertation examines approaches to improving the time and en-ergy efficiency of storing and processing data on embedded computing de-vices used for agricultural, environmental, and industrial monitoring. Thesystems developed work on the smallest, low-cost devices allowing for thesystems to be more easily and cost-effectively deployed. The data indexingstructures operate on many devices and storage types and are optimized forthe highest performance given the hardware capabilities.ivPrefaceAll the work presented henceforth was conducted at the Computer Sciencedepartment, University of British Columbia and supervised by Dr. RamonLawrence. Early versions of this manuscript were reviewed by the membersof the dissertation supervisory committee Dr. Yves Lucet and Dr. KhaladHasan.The linear hash study in Section 2.7.3 was conducted jointly with my su-pervisor Dr. Ramon Lawerence, Matthew Fritter, Andrew Feltham, SpencerMacBeth and Scott Fazackerley. This work appeared in two publications:− Andrew Feltham, Nadir Ould-Khessal, Spencer MacBeth, Scott Faza-ckerley, Ramon Lawrence. “Linear Hashing Implementations for FlashMemory”. Enterprise Information Systems. Springer. Invited and re-vised papers of ICEIS 2019. 386-405. ISBN 978-3-030-40783-4. DOI:10.1007/978-3-030-40783-4 18, Feb 2020.− Matthew Fritter, Nadir Ould-Khessal, Scott Fazackerley, and RamonLawrence. “Experimental Evaluation of Hash Function Performanceon Embedded Devices”, IEEE Canadian Conference on Electrical andComputer Engineering (CCECE 2018), Quebec City, QC, Canada,May 2018, pages 1-4, DOI: 10.1109/CCECE.2018.8447870.The results in Chapter 4 are joint work with my supervisor Dr. RamonLawrence and Scott Fazackerley and appeared in two publications:− Nadir Ould-Khessal, Scott Fazackerley, Ramon Lawrence. “Perfor-mance Evaluation of Embedded Time Series Indexes Using Bitmaps,Partitioning, and Trees”. Sensor Networks. Springer. Invited and re-vised papers of SENSORNETS 2021. Communications in Computerand Information Science, vol 1674.125-151. ISBN 978-3-031-17717-0.DOI: 10.1007/978-3-031-17718-7 7, Sept 2022.− Scott Fazackerley, Nadir Ould-Khessal, and Ramon Lawrence. “Ef-ficient Flash Indexing for Time Series Data on Memory-constrainedEmbedded Sensor Devices”, 10th Intl. Conference on Sensor Networksv(SENSORNETS’21), Feb. 2021, ISBN 978-989-758-489-3, pages 92-99,DOI:10.5220/0010318800920099.Chapter 5 is adapted from the published work jointly conducted withmy supervisor Dr. Ramon Lawerence and Scott Fazackerley.− Nadir Ould-Khessal, Scott Fazackerley, and Ramon Lawrence. “AnEfficient B-tree Implementation for Memory-Constrained EmbeddedSystems”, The 19th Int’l Conf on Embedded Systems, Cyber-physicalSystems, and Applications (ESCS’21).Some components of this dissertation are from these publications. Gen-erative AI was not used in any of the research except for grammar checking.viTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xivDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Chapter 2: Background . . . . . . . . . . . . . . . . . . . . . . . 52.1 Database Systems . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Embedded System Hardware . . . . . . . . . . . . . . . . . . 72.3 Flash Memory Architecture and Operations . . . . . . . . . . 92.3.1 Capacity and Reliability of Flash Memory . . . . . . . 92.3.2 NOR vs NAND . . . . . . . . . . . . . . . . . . . . . . 102.3.3 NAND Memory Chip . . . . . . . . . . . . . . . . . . 122.4 Flash-based Data Storage . . . . . . . . . . . . . . . . . . . . 132.5 Flash-based Storage and Database Systems . . . . . . . . . . 152.5.1 FTL flash-based DBMS . . . . . . . . . . . . . . . . . 162.5.2 Log-structured flash-based DBMS . . . . . . . . . . . 16viiTABLE OF CONTENTS2.6 Embedded Databases . . . . . . . . . . . . . . . . . . . . . . . 172.6.1 SQLite . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.6.2 Oracle Berkeley DB . . . . . . . . . . . . . . . . . . . 192.6.3 McObject eXtremeDB . . . . . . . . . . . . . . . . . . 192.6.4 ITTIA DB SQL embedded . . . . . . . . . . . . . . . 202.6.5 Antelope . . . . . . . . . . . . . . . . . . . . . . . . . 202.6.6 LittleD . . . . . . . . . . . . . . . . . . . . . . . . . . 202.7 Indexing Schemes on Flash Memory . . . . . . . . . . . . . . 212.7.1 FTL-based B-trees . . . . . . . . . . . . . . . . . . . . 212.7.2 Raw Flash B-tree variants . . . . . . . . . . . . . . . . 232.7.3 Linear Hashing . . . . . . . . . . . . . . . . . . . . . . 262.7.4 Sequential and Specialized Indexes . . . . . . . . . . . 30Chapter 3: Research Summary . . . . . . . . . . . . . . . . . . 323.1 Embedded System Environment . . . . . . . . . . . . . . . . 323.2 Research Outcomes . . . . . . . . . . . . . . . . . . . . . . . . 33Chapter 4: Indexing Sequential Data . . . . . . . . . . . . . . . 354.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . 354.2 Indexing Approach . . . . . . . . . . . . . . . . . . . . . . . . 374.2.1 Data Record Storage . . . . . . . . . . . . . . . . . . . 374.2.2 Design Optimized Value Indexing . . . . . . . . . . . . 384.2.3 Querying by Timestamp . . . . . . . . . . . . . . . . . 404.2.4 Querying by Value . . . . . . . . . . . . . . . . . . . . 404.2.5 Memory Management . . . . . . . . . . . . . . . . . . 424.2.6 Handling Variability . . . . . . . . . . . . . . . . . . . 424.2.7 Wear Leveling . . . . . . . . . . . . . . . . . . . . . . 424.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.4 Sequential Indexing Benchmarking . . . . . . . . . . . . . . . 464.5 Theoretical Performance Analysis . . . . . . . . . . . . . . . . 584.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 594.6.1 Insert Performance . . . . . . . . . . . . . . . . . . . . 614.6.2 Timestamp Query Performance . . . . . . . . . . . . . 644.6.3 Data Query Performance . . . . . . . . . . . . . . . . 664.6.4 Results Discussion . . . . . . . . . . . . . . . . . . . . 68Chapter 5: B+tree Indexing . . . . . . . . . . . . . . . . . . . . 715.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.2 B-tree Implementation . . . . . . . . . . . . . . . . . . . . . . 725.2.1 Example and Analysis . . . . . . . . . . . . . . . . . . 73viiiTABLE OF CONTENTS5.3 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 765.3.1 Insert and Query Performance . . . . . . . . . . . . . 765.3.2 Memory Buffering . . . . . . . . . . . . . . . . . . . . 775.3.3 Example Use Case . . . . . . . . . . . . . . . . . . . . 79Chapter 6: VMtree . . . . . . . . . . . . . . . . . . . . . . . . . . 826.1 Motivating Environment . . . . . . . . . . . . . . . . . . . . . 856.2 B-tree Optimizations . . . . . . . . . . . . . . . . . . . . . . . 876.2.1 Buffering and Logging . . . . . . . . . . . . . . . . . . 876.2.2 Virtual Mappings . . . . . . . . . . . . . . . . . . . . . 886.2.3 Page Overwriting . . . . . . . . . . . . . . . . . . . . . 906.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 906.3.1 Virtual Mappings . . . . . . . . . . . . . . . . . . . . . 906.3.2 Free Space Management . . . . . . . . . . . . . . . . . 916.3.3 Page Overwriting . . . . . . . . . . . . . . . . . . . . . 926.3.4 Recovery . . . . . . . . . . . . . . . . . . . . . . . . . 926.3.5 Implementation Variants . . . . . . . . . . . . . . . . . 93Chapter 7: VMtree Results . . . . . . . . . . . . . . . . . . . . . 957.1 Random Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 967.2 Sensor Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037.3 Optimizing Memory Usage . . . . . . . . . . . . . . . . . . . 1057.4 Varying Data Size . . . . . . . . . . . . . . . . . . . . . . . . 1107.5 Varying SD Card Hardware . . . . . . . . . . . . . . . . . . . 1117.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111Chapter 8: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 1148.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1148.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 115Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117ixList of TablesTable 2.1 Time Series Data stored in tsdata Table . . . . . . . . 6Table 2.2 Storage Media Specifications . . . . . . . . . . . . . . . 14Table 4.1 Index Parameters . . . . . . . . . . . . . . . . . . . . . 37Table 4.2 Comparative Analysis Size and Memory Usage . . . . 44Table 4.3 Comparative Analysis of I/Os . . . . . . . . . . . . . . 44Table 4.4 Theoretical Index Performance . . . . . . . . . . . . . 58Table 4.5 Hardware Performance Characteristics . . . . . . . . . 60Table 4.6 Index I/O Metrics for Insert Experiment - PercentageAdditional I/Os Compared to Data File Size . . . . . 62xList of FiguresFigure 2.1 CREATE TABLE statement for tsdata . . . . . . . . 6Figure 2.2 Example SQL Query on Time Series Data . . . . . . 6Figure 2.3 Conventional MOSFET transistor . . . . . . . . . . . 10Figure 2.4 Floating Gate MOSFET transistor . . . . . . . . . . . 11Figure 2.5 NAND vs NOR cell array . . . . . . . . . . . . . . . . 11Figure 2.6 NAND Memory Chip Structure . . . . . . . . . . . . 12Figure 2.7 2 GB NAND Flash with 2048 Blocks . . . . . . . . . 13Figure 2.8 Wandering Tree . . . . . . . . . . . . . . . . . . . . . 24Figure 2.9 µ-Tree Update Example . . . . . . . . . . . . . . . . . 25Figure 2.10 Lazy Adaptive Tree . . . . . . . . . . . . . . . . . . . 26Figure 2.11 In-Page Logging Architecture . . . . . . . . . . . . . . 27Figure 2.12 Example linear hash table with hash keys . . . . . . . 28Figure 2.13 Example of linear hash table with hash keys after asplit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Figure 4.1 Example of A Periodically Sampled Time Series Data 36Figure 4.2 SBITS Page Structure ID: 4 bytes Page ID, Start:4 bytes UNIX smallest timestamp value in seconds,End: 4 bytes UNIX Largest timestamp value in sec-onds, Cnt: 2 bytes count of records in page, Max: 2bytes Max value in page , Min: 2 bytes Min value inpage, Sum: 4 bytes sum of values in page, Bmap: 2bytes Bitmap index . . . . . . . . . . . . . . . . . . . 39Figure 4.3 Querying by Value Range . . . . . . . . . . . . . . . . 41Figure 4.4 Frontier Advance Wear Leveling . . . . . . . . . . . . 43Figure 4.5 Range Partitioning Example . . . . . . . . . . . . . . 48Figure 4.6 Partition Algorithm Implementation . . . . . . . . . . 50Figure 4.7 B-tree Primary Index on Timestamp . . . . . . . . . 52Figure 4.8 B-tree Secondary Index on Data Value . . . . . . . . 53Figure 4.9 Bitmap Index on Time Series Data . . . . . . . . . . 55Figure 4.10 Querying by Value Range . . . . . . . . . . . . . . . . 57xiLIST OF FIGURESFigure 4.11 Index Insert Performance on ATmega2560 . . . . . . 61Figure 4.12 Index Insert Performance on 32-bit Platform usingDataFlash . . . . . . . . . . . . . . . . . . . . . . . . 64Figure 4.13 Index Insert Performance Compared to Sequential File 65Figure 4.14 Index Timestamp Query Performance on ATmega2560 65Figure 4.15 Timestamp Query Performance on 32-bit platformwith DataFlash Memory . . . . . . . . . . . . . . . . 66Figure 4.16 Index Data Query Performance on ATmega2560 . . . 67Figure 4.17 Index Data Query I/O Performance . . . . . . . . . . 68Figure 4.18 Relative Data Query Performance on All Platforms . 69Figure 5.1 B-tree Insert Implementation . . . . . . . . . . . . . . 73Figure 5.2 B-tree Split Implementation . . . . . . . . . . . . . . 74Figure 5.3 B-tree Before Insert of 165 . . . . . . . . . . . . . . . 75Figure 5.4 B-tree After Insert of 165 . . . . . . . . . . . . . . . . 75Figure 5.5 B-tree Insert Time . . . . . . . . . . . . . . . . . . . . 77Figure 5.6 B-tree Insert I/O . . . . . . . . . . . . . . . . . . . . 78Figure 5.7 B-tree Query Time . . . . . . . . . . . . . . . . . . . 78Figure 5.8 B-tree Query I/O . . . . . . . . . . . . . . . . . . . . 79Figure 5.9 B-tree Time Performance with Increasing Memory . . 80Figure 5.10 B-tree I/O Performance with Increasing Memory . . . 80Figure 6.1 B+-tree Example . . . . . . . . . . . . . . . . . . . . 82Figure 6.2 Example Embedded Devices compared with OriginalExperimental B-tree Hardware in 1970 . . . . . . . . 85Figure 6.3 Inserting Key 50 . . . . . . . . . . . . . . . . . . . . . 94Figure 7.1 Embedded Devices Hardware Configurations . . . . . 95Figure 7.2 Embedded Devices Storage Performance . . . . . . . 95Figure 7.3 Experimental Data Sets . . . . . . . . . . . . . . . . . 96Figure 7.4 Insert Performance on SD Card Compared to B-Tree(ARM) . . . . . . . . . . . . . . . . . . . . . . . . . . 97Figure 7.5 Insert Performance on Dataflash Compared to B-Tree(ARM) . . . . . . . . . . . . . . . . . . . . . . . . . . 97Figure 7.6 Insert Performance with Varying Number of Log Bufferon SD Card (ARM) . . . . . . . . . . . . . . . . . . . 99Figure 7.7 Insert PerformanceWith Varying Number of Log Bufferson Dataflash (ARM) . . . . . . . . . . . . . . . . . . . 100Figure 7.8 Insert ThroughputWith Varying Number of Log Buffers(ARM) . . . . . . . . . . . . . . . . . . . . . . . . . . 101xiiLIST OF FIGURESFigure 7.9 Insert Performance on SD Card and NAND Memory(PIC) . . . . . . . . . . . . . . . . . . . . . . . . . . . 102Figure 7.10 Relative Insert Bandwidth on NAND and SD CardWith Varying Number of Log Buffers (PIC) . . . . . 102Figure 7.11 Insert Throughput Temperature Data (ARM) . . . . 104Figure 7.12 Insert Throughput Health Data (ARM) . . . . . . . . 106Figure 7.13 Insert Throughput Temperature and Health Data (PIC)107Figure 7.14 Write Throughput With Varying Memory (ARM) . . 108Figure 7.15 Read Throughput With Varying Memory (ARM) . . 109Figure 7.16 Write Throughput for Larger Data Sets (ARM) . . . 112xiiiAcknowledgementsI would like to express my thanks and gratitude to my dissertation super-visor, Dr. Ramon Lawrence for his guidance, advice and continuing supportthroughout my doctoral study program. His generous and constructive feed-back had a direct impact on the success of this work and will continue to bea source of inspiration.My thanks to all my colleagues, members of the database research groupin the Computer Science Department especially Dr. Scott Ronald Fazack-erley.I wish to also extend my thanks and gratitude to the dissertation com-mittee members Dr. Yves Lucet and Dr. Khalad Hasan from the I. K.Barber Faculty of Science for their guidance and support, my university ex-aminer Zheng Liu, School of Engineering and the external examiner IoanisNikolaidis, Faculty of Science, University of Alberta.I also would like to acknowledge the support of Okanagan College andthe University of British Columbia College of Graduate Studies for theirsupport of this research.Finally, I would like to thank my family for their ongoing support andpatience over the past years. This work would not have seen the light of daywithout the support, encouragement and dedication of my partner. Thankyou Mrs. Ok.xivDedicationTo Michelle, Ouahiba, Waseem, Hana and Zaki with all my love.xvChapter 1IntroductionTo improve performance, database management system designers aim attaking full advantage of the storage medium features while circumventing itslimitations. Early database systems were designed to take advantage of themagnetic hard disk drive’s large capacity and random access capability tostore and retrieve large amounts of data at a relatively high speed despite thedrive’s moving mechanical parts. As technology moved towards flash-basedsemiconductor storage devices such as Solid State Drives, memory cardsand USB drives, database system design needed to adapt to the intrinsiccharacteristics and operating constraints of flash memories.Semiconductor storage offers several advantages over hard drives includ-ing low power, small form factor and low latency data transfer. At thesame time, storage management techniques need to address flash memoryconstraints such as erase-before write, erase unit size, read and write pagegranularity, and the limited number of erases over the device’s lifespan.Embedded devices used in sensor networks, Internet of Things, andcyber-physical systems use flash storage with limited computational powerand memory hardware. Developing efficient data management techniquesfor these small devices can save considerable energy, cost, and resources fordeployment.Database systems are complicated software that rely on support fromthe hardware and the operating system. Unlike server-based systems, adatabase on an embedded system may not have operating system supportand may be responsible for low-level storage management. This compli-cates the development of these systems, and results in many applicationsdeveloping their own data storage code rather than using existing libraries.The focus of this thesis is database systems and indexes for the smallestembedded devices that are not well-supported currently. Sensor devices andsmall embedded processors are several orders of magnitude smaller thanmobile devices like smartphones, and often cannot run existing embeddeddatabase system software.11.1. MOTIVATIONS1.1 MotivationsSensor devices typically collect time series data consisting of records witha timestamp and one or more data values. An embedded database requirestwo types of indexes to support this type of data. Sequential indexing is usedwhen indexing on the timestamp value in the record as this data is in sorted,increasing order. This sorted order can be leveraged to develop more efficientindex structures. On the other hand the data values are not in sorted order,although they may vary in relatively predictable patterns if the sensor ismonitoring the physical environment (i.e. temperature changes relativelyslowly) and will require a different type of index. The B-tree [BFJ+15] isthe most commonly used index in indexing non-sorted data.This thesis contributes to both index types. For sequential indexing, theSequential Binary Index for Time Series (SBITS) is proposed and evaluatedagainst prior embedded indexes that used sorted files, trees, and hashing[OKFL20]. SBITS has the highest performance given its memory use forboth key and data value queries.There has been considerable prior research on adapting the B-tree in-dex [BFJ+15] to flash based storage such as solid-state drives (SSDs). Asurvey of flash indexing [FABM20] overviews over 30 different implementa-tions. The general goal is to reduce the number of expensive flash writesby using available memory to defer writes and allow for batching and se-quential writes. Systems use either a logging approach [KL15, NLM12,RKLP14, WKC07a] or buffer page updates before writing [BFJ+15]. Thelatest, highest performing algorithms exploit the inherent parallelism inSSDs [FABM20].Implementing a B-tree for a memory-constrained embedded devices suchas sensor devices, has unique challenges compared to indexing on servers.The most significant issue is the extremely limited memory. This requiresan algorithm to consider its total memory consumption beyond just thememory used for data buffers. Memory used for implementation and statevariables is important. Although the data sizes processed are orders ofmagnitude smaller, the relative RAM versus storage ratio is lower. Typicalservers have at least 1% RAM compared to the data storage size, and manydeployments have enough memory to store a large percentage of the data set[AGBA19]. An embedded device may have less than 1% memory comparedto the data size, and the absolute memory size is very small. Every bytecounts in this environment.The second factor is the flash storage may consist of raw flash memorychips rather than packaged products like SD cards or solid-state drives. This21.2. CONTRIBUTIONSaffects implementations in two important ways. First, the implementationmust handle the allocation and management of physical memory pages onthe devices including wear leveling, page placement, and free space man-agement. Without a flash translation layer (FTL) [CPP+09], the algorithmmust map logical page addresses to physical pages while consuming a min-imum amount of memory for this operation. Secondly, there are less op-portunities for parallelism. The CPU is usually single-threaded, the storagedevice can only respond to one request at a time, and transferring data onthe bus is a bottleneck. I/O performance is limited by the bus speed ratherthan the storage device bandwidth. The low memory available restrictsB-tree approaches [FABM20] developed for raw flash that assume memorysizes available on servers.1.2 ContributionsThis thesis develops several B+tree variants optimized for embeddedsystems. The first B+tree version was able to function on small embeddeddevices while utilizing only two page buffers and less than 2 KB of RAM.However, this version required SD card storage with a flash translation layer(FTL). An improved version, called VMtree, implemented multiple storage-optimized variants that allowed it to work with various types of storageincluding SD cards, NOR memory supporting overwriting, and raw NANDflash memory. The result was a B+tree implementation adaptable to thestorage characteristics that significantly outperforms the state-of-the-art im-plementations while executing on the smallest devices.Overall, the contributions of this thesis are:− A sequential index called SBITS that outperforms prior tree and hash-based approaches when indexing sequential, time series timestamps.− An analytical and experimental comparison of SBITS versus sortedfiles, trees, and hashing.− A B+tree implementation that consumes minimal memory when usedon embedded devices with SD card storage.− A storage-adaptive B+tree implementation called VMtree capable ofdeployment on a wide variety of storage devices including SD cards,NOR, and NAND flash memory. VMtree is capable of deployment onraw storage not previously possible with other embedded indexes.31.2. CONTRIBUTIONS− VMtree implements an approach to reducing write amplification forB-tree updates by using virtual mappings. Virtual mappings allowphysical page movements without rebuilding the index structure.− A B-tree variant designed for memory supporting page overwritingsuch as NOR and Dataflash [Ade24].− An experimental evaluation on two hardware platforms and threememory types showing the benefits of storage-specific B-tree optimiza-tions to maximize performance on hardware with unique properties.SBITS has been deployed as the storage and index architecture for the em-bedded database EmbedDB. EmbedDB is available on GitHub at https://github.com/ubco-db/EmbedDB. The source code for the VM-tree and B-tree are at https://github.com/ubco-db/vmtree and https://github.com/ubco-db/btree respectively.The organization of the thesis is as follows. Chapter 2 provides back-ground on database systems, embedded devices, flash memory, and imple-mentations of indexing and databases on embedded systems. Chapter 3presents an overall research summary discussing the research motivations,environment, and key goals. Sequential indexing is covered in Chapter 4including presenting SBITS and its comparison to prior work. Chapter 5presents a low-memory implementation of the B+tree index for embeddeddevices with SD card storage. This implementation is extended to supportmultiple storage types, including NAND flash and NOR supporting dataoverwrites, in VMtree discussed in Chapter 6. Extensive results compar-ing VMtree variants on multiple hardware platforms and data sets are inChapter 7. The thesis closes with conclusions and future work.4Chapter 2Background2.1 Database SystemsA database system is software that provides abstraction on how datais stored, queried, and updated on a computer. Modern database systemsare large software systems often consisting of millions of lines of code. Toprovide data abstraction from the implementation details, the structure ofa database is defined using a data model. A data model is a way of orga-nizing the data. The most common data model is the relational model thatorganizes data as relations, or tables. Tables are comprised of rows andcolumns. Each row represents a distinct record, often referred to as a tuple,while each column defines a specific attribute or field within those records.These columns dictate the permissible data types that can be stored withinthem, encompassing a wide range from text to numerical values and dates.There are many different data models including object-oriented, graphs, andtrees, but the relational model is sufficient for this thesis.As an example, consider representing a time series data set, which willbe used in this work. A time series record would consist of a timestampvalue when the data was collected and one or more data values such astsdata(ts, val1, val2, val3), where in this example tsdata is the name of thetable, ts is the column storing the timestamp, and val1, val2, val3 are thedata points collected at that time. An example data set is in Table 2.1.Defining the relational structure and executing queries requires a datadefinition and manipulation language, such as SQL. Using SQL, the tsdatarelation can be constructed using a CREATE TABLE statement (Figure 2.1)and queries executed using a SELECT statement (e.g. in Figure 2.2).Data abstraction is achieved by separating how the data is stored andorganized in the system from its external interface defined in the data model.When the user executes the SQL query in Figure 2.2, they do not need tounderstand how the data is represented in the system and the process thatthe database system will perform to return the answers to their query.Internally, the database translates an SQL statement into relational alge-bra operations first proposed by E.F. Codd in 1970 [Cod70]. This relational52.1. DATABASE SYSTEMSts val1 val2 val32024-06-01 12:00:00 20 0 02024-06-01 13:00:00 21 5 02024-06-01 14:00:00 22 2 02024-06-01 15:00:00 23 0 02024-06-01 16:00:00 26 25 02024-06-01 17:00:00 27 30 1002024-06-02 03:00:00 13 5 02024-06-02 04:00:00 12 3 02024-06-02 05:00:00 10 1 502024-06-02 06:00:00 12 7 100Table 2.1: Time Series Data stored in tsdata TableCREATE TABLE tsdata (ts timestamp PRIMARY KEY ,val1 integer ,val2 integer ,val3 integer);Figure 2.1: CREATE TABLE statement for tsdataalgebra expression is then optimized and translated into an execution plan.It is during this translation and optimization that the database system ex-plores different algorithms and techniques to efficiently answer the query.The primary focus of this work is on indexes that improve query per-formance when retrieving a subset of the data. For example, the query inFigure 2.2 is retrieving only a subset of the data in the tsdata table whenthe value of val1 >= 25. A simple way of executing this query would be toscan each row in the data set, test the filter condition, and only return therow if it passes the conditional test. An index makes this more efficient byonly accessing the records required without needing to scan all records.SELECT ts, val1 , val3FROM tsWHERE val1 >= 25Figure 2.2: Example SQL Query on Time Series Data62.2. EMBEDDED SYSTEM HARDWARE2.2 Embedded System HardwareWhen microprocessors were first designed they were not intended for PCsor laptops, the early processors were designed to replace digital logic chipsembedded in a calculator. Instead of hundreds of integrated circuits (ICs),a single microprocessor IC embedded within the portable calculator wasused to perform arithmetic logic operations, manage the memory and drivethe peripherals (keypad and seven-segment display). These days embeddedcomputing systems can be found almost everywhere from personal devicessuch as watches, cell phones, household appliances and cars to industrialapplications such as environmental sensor networks and swarm drone robots.Further, embedded systems are at the core of new technologies such ascyber-physical systems (CPS) where computational devices (embedded sys-tems) are integrated with the dynamic physical environment of the appli-cation [Lee07] and Internet of Things (IoT) where embedded devices sharesensors and control actuators through the Internet.Embedded computing systems are not always built around micropro-cessors. Several other technologies have been used including Field Pro-grammable Gate Arrays (FPGAs) and Application Specific Integrated Cir-cuits (ASICs). However, the use of processors is widespread due to their highefficiency. Programmability is another distinguishing factor of processor-based systems, as the same CPU hardware can be used to design differentembedded devices by simply programming or downloading new code.Design of embedded system device hardware must meet several opera-tional, physical, environmental and budgetary requirements. Among theseis the real-time response to changes in the devices’ perceived environment.The physical constraints include size, shape and weight to fit within themechanical structure of small and portable devices such as hearing aids,toothbrushes and invasive surgical devices. Contrary to general-purposecomputing systems such as PCs, servers and laptops which are usually lo-cated in a structured environment with controlled temperature and stablepower source, most embedded devices such as sensor networks are deployedin harsh environments and subject to adverse weather and physical condi-tions. Cost is another design criterion, as these devices are usually deployedoff the grid, they rely on limited capacity batteries to provide the needed en-ergy. As such these devices must use energy-efficient hardware such as low-power processors running efficient software. Other budgetary constraintsinclude limited main and storage memory due mainly to chip size and cost.Processor-based Embedded Systems are built around either general purposeMicro Processor Units (MPUs) or dedicated Micro Controller Units (MCUs).72.2. EMBEDDED SYSTEM HARDWAREMCUs include in addition to the CPU, data and program memory as wellas several dedicated built-in peripherals such as analog to digital convert-ers, timers, counters and various communication modules. Microcontrollerscome in various sizes, capabilities, and architectures however they share thefollowing properties:− Low memory: due the small footprint of these MCUs the size of thesilicon portion set aside for memory is small. additionally certainmemory technologies such as SRAM are low density.− Low energy: most of these devices are single core low speed MCUswith limited computational power.Embedded devices based on MCUs have little memory to run applica-tions and require efficiently designed programs. Currently the most com-monly used MCUs include:− PIC10F/PIC12F/PIC16F [Mic]: Microchip®’s PIC microcontrollersare known for their compact size and low power consumption, mak-ing them suitable for various embedded applications where space andpower consumption are critical.− ATtiny Series [AVR]: Produced by Microchip® (formerly Atmel), theATtiny series offers a range of small, low-power microcontrollers suit-able for many embedded applications.− STM32F0 Series [STM]: STMicroelectronics’ STM32F0 series offers arange of small, low-power microcontrollers based on the ARM Cortex-M0 core, suitable for various applications including IoT and wearables.− ESP8266/ESP32 [ESP]: While primarily known for their Wi-Fi capa-bilities, these microcontrollers also offer powerful processing capabili-ties in a compact form factor, making them suitable for IoT devices.− NXP LPC800 Series [LPC]: The LPC800 series offers small form-factormicrocontrollers with ARM Cortex-M0+ cores, suitable for applica-tions requiring low power and compact size.− Raspberry Pi Pico [Buy]: While not strictly a microcontroller in thetraditional sense, the Raspberry Pi Pico is a microcontroller boarddeveloped by the Raspberry Pi Foundation featuring a compact sizeand a powerful RP2040 microcontroller chip.82.3. FLASH MEMORY ARCHITECTURE AND OPERATIONS2.3 Flash Memory Architecture and OperationsFlash memory is a non-volatile Electrically Erasable Programmable ReadOnly Memory (EEPROM). The memory technology is based on the float-ing gate cell architecture where each memory cell consists of a floating gatetransistor capable of storing electrical charge indefinitely (Figure 2.4). Com-pared to the conventional MOSFET (Figure 2.3) the floating gate MOSFET,Figure 2.4, structure features two gates, namely a control gate and a floatinggate. The floating gate is made of a polysilicon (Poly-Si) gate encapsulatedin an insulator, Silicon Dioxide (SiO2). Charges can be stored permanentlyin the Poly-Si gate without the need to refresh circuitry or charge power.This feature is the main reason behind the wide use of floating gate transis-tors in non-volatile memory such as EEPROMs and Flash. Charges storedin the Poly-Si gate, QFG, can be a result of UV-exposure, application oflarge voltage across the silicon dioxide layer or by injecting electrons usinghot-electron injection [CMMS08]. Reading the memory cell is achieved byapplying an intermediate threshold voltage to the word-line (control gateVG) which will result in the absence (bit 0) or the presence (bit 1) of aDrain-Source current IDS depending on the presence or absence of the float-ing gate charge QFG.Writing to the memory cell is split into two phases:Phase 1: Erasing a memory cell (storing a 1 in the case of SLC memorycells) amounts to removing the negative charge in the floating gate of thetransistor. When a high negative VGS is applied to the cell it removes thenegative charge QFG from the floating gate. The negative charges tunnelthrough the thin SiO2 insulator layer from the floating gate towards thep-substrate in a process referred to as Fowler-Nordheim (FN) tunnelling[FN28].Phase 2: Programming, setting a bit to “0”, is injecting negativecharges into the floating gate. In the case of NOR memory cells this is doneby accelerating the electrons in the channel (applying a high VDS voltageand a High positive VGS voltage) allowing high energy electrons to tunnelthrough the SiO2, Channel Hot Electron injection (CHE) [BCS92]. ForNAND, FN tunnelling is used to move electrons from the channel to thefloating gate by applying a high positive VGS .2.3.1 Capacity and Reliability of Flash MemoryThe floating gate cell architecture is employed in designing flash mem-ories with various densities including Single Level Cells (SLC) with 1 bit92.3. FLASH MEMORY ARCHITECTURE AND OPERATIONSper cell, Multi Level Cells (MLC) with 2 bits per cell, Triple Level Cells(TLC) with 3 bits per cell, and eXtended Level Cells (XLC) or Quad levelcells(QLC) with 4 bits per cell. While density and cost efficiency tend toimprove as the number of bits per cell increases, data storage reliability isadversely affected in at least three distinct ways:− Endurance or cycling (number of program/erase cycles): SiO2 insula-tor will degrade and electrons could be trapped in the SiO2 reducingthe threshold voltage difference between Erase and Program.− Stress Induced Leakage Current: reduces the retention of charges inthe FG due to electrons trapped in the SiO2 which will create a con-duction path hence leakage of charges and loss of data [SHHA98].− Read-disturb: Read disturb is a side effect of the process of readingdata from a single flash cell. Applying voltages higher than the thresh-old voltages of unselected rows can cause these voltages to shift to ahigher value due to weak programming effect [CLGM15].Figure 2.3: Conventional MOSFET transistor2.3.2 NOR vs NANDThere are several key definitions related to flash memory:− Page - The smallest addressable unit for read and write operations.− Block - A block consists of multiple pages and is the smallest address-able unit for erase operations.102.3. FLASH MEMORY ARCHITECTURE AND OPERATIONSFigure 2.4: Floating Gate MOSFET transistor− Logical unit number (LUN) - The minimum unit that can indepen-dently execute commands and report status. There are one or moreLUNs per NAND target.− Page register - Register used to read data that was transferred fromthe Flash array. For program operations, the data is placed in thisregister prior to transferring the data to the Flash array.Two main types of flash memory devices have emerged over the years,namely NOR and NAND flash memories. NAND Flash cells are 60% smallerthan NOR Flash cells, providing higher densities. This is due to the struc-ture of cell arrays; whereas the contacts of NOR Flash occupy a much largerpercentage of the array than that of the NAND contact (see Figure 2.5).Figure 2.5: NAND vs NOR cell array112.3. FLASH MEMORY ARCHITECTURE AND OPERATIONSFigure 2.6: NAND Memory Chip StructureNOR Flash is addressed at the byte-level granularity, whereas NANDFlash is addressed at the page-level granularity. Due to its structure, NORFlash read performance is higher than write performance which makes thistype of non-volatile memory ideal for firmware and executable code storage.2.3.3 NAND Memory ChipA typical NAND memory chip contains 1, 2 or 4 planes, as shown inFigure 2.6. Each plane consists of several blocks depending on the memorymodel and capacity. Each block consists of flash memory pages. The pagerepresents the read and write granularity of a NAND chip and stores bothuser data and metadata. It is divided into User Date Area (UDA) space(the largest) and Out Of Bound (OOB) space.OOB space stores metadata regarding the user data such as parity infor-mation for error correction (ECC), logical page number, bad block markers,address translation and other FTL (Flash Translation Layer) parameters.In addition to the NAND array, the plane contains a register called apage buffer or a page register. The size of the register is equal to that ofthe flash page. The page buffer is used to transfer data between the NANDarray and the host device.Figure 2.7 shows a 2 GB NAND flash with 2048 blocks. Each block is64 pages with a page capacity of 2112 bytes including 2048 bytes for userdata and 64 bytes for spare data.122.4. FLASH-BASED DATA STORAGEFigure 2.7: 2 GB NAND Flash with 2048 Blocks2.4 Flash-based Data StorageFlash-based storage systems represent a major advancement in data stor-age technology, offering a versatile array of solutions tailored to diverse needsand applications. At one end of the storage spectrum are high-performanceand large-capacity Solid State Drives (SSDs), which have become integralcomponents of modern computing systems. These SSDs boast significantstorage capacities, surpassing traditional mechanical hard drives, while of-fering unparalleled speed and reliability. They are the backbone of manydesktop computers, laptops, and servers, powering everything from everyday to enterprise computing tasks.At the opposite extreme, we encounter compact but indispensable flashstorage options utilized in portable gadgets like smartphones, digital cam-eras, tablets, and handheld devices. Despite their small size, Secure Digital(SD) cards, Flash Drives and Multimedia (MMC) cards pack a considerableamount in terms of storage capacity.This widespread adoption of flash-based storage has transformed thelandscape of data storage, ushering in an era of faster access times, lowerpower consumption, and increased durability compared to traditional mag-netic storage solutions. However, in designing flash-based storage manage-ment systems, it is crucial to take into consideration the intrinsic constraints132.4. FLASH-BASED DATA STORAGEof flash memory technology that differentiate it from magnetic storage:− Erase-Constraint: As discussed earlier, to store a bit in a flash-basedmemory cell it must be first erased. This is a fundamental issue withflash-based storage where an area (page) cannot be overwritten unlessthe block that contains the page has been erased.− Write Granularity Constraint: The minimum unit of write operationin flash is a page. Both NAND devices in Table 1 have 2 KB pages.− Sequential Page Write Constraint: Pages on flash can only be writtenin sequential order.− Wear-Constraint: The number of times a block can be written orerased is limited. In Table 1, both NAND devices have 100,000 en-durance.− Asymmetric Read/Write Operations: In the case of HDD, read andwrite operations are almost identical as they both equally depend onthe seek time, rotation time and transfer bandwidth (in Table 2.2,both read and write take 4.17ms for Toshiba X300 HDD). In NAND-based devices, reading is as much as ten times faster than writing.Additionally, the write operation consumes more energy than the readoperation [LAH03].Storage Media Operation W25N01GVNANDMT29F2G08NANDToshibaX300 HDDGranularityRead 1 byte 1 byte SectorWrite 2048 bytes 2048 bytes SectorErase 128k 128k -Access TimeRead 25 µs 25 µs 4.17 msWrite 250 µs 300 µs 4.17 msErase 2 ms 2 ms -Sequential Page Write Yes Yes NoEndurance (write/erase cycles) 100,000 100,000 -Table 2.2: Storage Media SpecificationsTo address these drawbacks of flash memory two main approaches havebeen followed in the implementation of flash-based storage:− Block-based emulators approach enabling applications such as file sys-tems to run just like they did on a disk-based storage systems. An142.5. FLASH-BASED STORAGE AND DATABASE SYSTEMSintermediary layer between data management applications such asFAT16 and the memory array is used to emulate block-based oper-ations and abstract the underlying complexities of the memory arraymanagement. This software layer comes in the form of firmware run-ning on the NAND Flash Memory Controller (Memory Technology De-vice) providing low-level functionalities such as read, write and erase.High-level management algorithms, such as logical/physical addresstranslation, garbage collection, and wear leveling, are implemented bya flash translation layer (FTL) [Int98]. As such any well-supportedblock-based (disk) file system such as FAT16, FAT32 and YAFS couldbe easily built to run over devices such as SD cards, CompactFlashand Smart-Media.− The second approach, the native file system approach, is similar tothe disk-based log-structured file system (LFS) [RO92] where all up-dates are recorded as appends to a log file with no overwriting. TheJournalling Flash File System (JFFS) [Woo01], which was designedto store files in flash storage on embedded systems, operates directlyon the memory array. File and metadata (such as file permissions,file ownership, etc.) writes are performed by writing (appending) newnodes to the end of the log. These nodes of data and metadata arestored sequentially on the raw flash memory until a garbage collectionis triggered. Garbage collection is triggered when either space is re-quired by the application before it is needed or when insufficient freespace is encountered when writing new nodes.2.5 Flash-based Storage and Database SystemsUnlike file system operations where reads and writes are confined to spe-cific regions in the storage, DBMS requests are characterized by randomaccess across the entire storage medium. This randomness poses challengesfor flash storage devices, as multiple write requests necessitate costly eraseoperations. Moreover, frequent erasures of the same blocks lead to memoryarray wear-out and the decrease of its lifetime, compromising the device’sreliability for long-term storage and transaction integrity. Another factorcomplicating DBMS operations on flash storage is the constraint imposedby block sizes. When data blocks (pages) are smaller than the erase blocksize (block), writing them requires a complex process: first, moving theerase-block-sized data block to main memory, updating the data block page,followed by erasing the corresponding block, and finally writing the updated152.5. FLASH-BASED STORAGE AND DATABASE SYSTEMSblock back to the storage medium. This process, known as in-place update,introduces latency and main memory overhead, impacting not only the effi-ciency of the DBMS but also its transaction integrity in case of power loss.To circumvent frequent block erasures, several out-of-place update methodshave been used and can be categorized into two major approaches: FTL-based and log-based.2.5.1 FTL flash-based DBMSThe Flash Translation Layer (FTL) [GT05, LM07] was optimized for filesystems to store and manage files rather than DBMS transactions. The roleof the FTL layer is to emulate flash memory as a block-oriented device thatcan operate the same as a disk. The FTL tasks can be summarized as:1. Updated pages are written to new (previously) erased blocks insteadof erasing a new block.2. Keep track of updated page addresses and divert subsequent reads topages in the new blocks (mapping between logical and physical pages).3. Select the new blocks (for page updates) so that blocks in the flashmemory are evenly distributed by distributing erase cycles across theentire memory array (wear leveling)4. Keep track of invalid blocks for future erasing (garbage collection).An update transaction invokes the FTL to write the updated logicalpage into a physical page. Since in-place update is very costly in flash-based storage systems due to the erase before write constraint, an out-placeupdate is used instead. Hence, to update records in physical page p1, thepage is first read into logical page l1. The updated logical page l1 is writteninto a new physical page p2 and the page p1 is marked obsolete. TheFTL garbage collection keeps track of obsolete pages and their reclamation.When a logical page is re-created from flash memory, it is read directly fromthe mapped physical page.2.5.2 Log-structured flash-based DBMSWith a log-structured approach (LSA), the DBMS has direct access tothe storage without an intermediary layer such as an FTL. Updates to thedatabase are stored in the form of log records and written to the end of the162.6. EMBEDDED DATABASESdatabase. Since logs are written sequentially to an erased section of mem-ory, write performance is good, regardless of the pattern of write requests[LKW+09]. Whenever logical pages are updated, the update logs of mul-tiple logical pages are collected into a buffer. When the buffer is full, it iswritten into a single physical page [KWS10a]. A logical page may thereforebe stored on multiple pages. To recover the database, the log records areapplied to reconstruct the most recent version by reading multiple pagesand merging the records to generate updated database pages.Another variation of the log-structured approach is In-Page Logging(IPL) where updates are logged at the end of the updated page block in-stead of the end of the database. To recover the most recent version of thedatabase, log records within the database page are applied to pages in thesame block [LM07]. IPL divides the pages in each block into original pagesand log pages. Updates are written to log pages within the same block ofthe original (physical) page. When recovering the original page, IPL readsthe original page and only the log pages in the same block. When there areno free pages in the block, the log pages are merged with the original pageand a new page is written to a new block. The use of in-memory buffersintroduces main memory overhead and loss of data in case of power fail-ure. Other variations of LSA include work on Page-differential [KWS10b],differed updates [DMLD10] and shadow-based storage [YP12a].2.6 Embedded DatabasesIn contrast to application-embedded databases that form the hiddenpart of an application, embedded databases (also known as deeply embed-ded) referred to in this thesis are lightweight databases capable of runningon embedded computing devices such as microcontrollers (MCUs). Thistype of database has seen a vast evolution thanks in part to consumer elec-tronics such as smartphones, PDAs and tablets and the emergence of newtechnologies such as smart sensors, Internet of Things, and cyber-physicalsystems. We distinguish between two types of embedded databases, thosethat are deployed on hardware devices with abundant memory and rela-tively fast CPUs and those that run on devices with limited memory andcomputational power. Smartphones and tablets are built using advancedmulti-core CPU architecture and large silicon memory space. Devices suchas Android or iPhone smartphones run on ARM processors at speeds mea-sured in GHz with large storage and memory space. These devices, whilesmall in footprint, have cost, memory, and computational power comparable172.6. EMBEDDED DATABASESto stand-alone computers.Cost and power become an issue in applications such as distributed smartsensors, where a large network of small-footprint sensors are deployed in asensor network [ASSC02, BCDV09]. Each node in the network is respon-sible for capturing its corresponding physical phenomena through the mea-surement of environmental properties (temperature, noise level, humidity,pressure, etc.). Databases used with these devices should be able to run oncost-effective hardware with limited power consumption, limited memoryresources and computational power. The CPU may be low-power 8-bit, 16-bit, or 32-bit with clock speeds between 16 MHz and 128 MHz and memorycapacity ranging from 4 KB to 128 KB.Efforts to boost the computational power of such devices through dis-tributed computing using wireless technology face significant challenges, pri-marily due to latency and power consumption. High latency can severelyimpact the performance of transactions that require real-time processingor rapid data exchange. Additionally, communication modules especiallythose handling wireless transmissions, consume a substantial amount ofpower. In battery-operated devices, this can lead to quicker depletion ofbattery life, limiting the usability and practicality of such a network [CES04,VCDSdM03].Compared to standard databases, embedded databases experience fail-ures that differ in both nature and frequency. These devices rely on on-boardbatteries, which are susceptible to failures and rapid depletion. Additionally,failures may occur due to frequent changes in environmental factors such ashigh humidity and extreme temperatures, necessitating efficient mechanismsfor initialization and crash recovery.Most of the embedded database management systems currently in usewere historically designed to run on standalone desktop computers. Severalof these DBMSs have been ported to run on embedded processors such asARM processors and Microchip microcontrollers. These embedded DBMSsoffer a range of functionalities, from full SQL support to key/value storage,catering to various needs in embedded systems. The most commonly usedembedded DBMS are described below.2.6.1 SQLiteSQLite [Owe06] is a well-established relational database widely used innearly all smartphones, including Android and iPhone [sql]. Written in ANSIC, SQLite runs on numerous platforms such as Linux, iOS, Windows, andAndroid. Its source code is in the public domain, allowing easy portability182.6. EMBEDDED DATABASESto other operating systems. SQLite is notable for its small footprint, beingless than 500 KiB in size. Another key feature is its minimal configurationrequirement since it operates as a server-less database. It is fast, reliable,and easy to install and use. The resulting database is stored in a singlefile, which can be written to flash disks, USB memory sticks, or SD cards.Given its small footprint, SQLite could be ported to virtually any 32-bitmicrocontroller. One such example is Samsung’s S3C44B0X [Samb], 32-bitARM7TDMI RISC microcontroller running at 66 Mhz.2.6.2 Oracle Berkeley DBBerkeley DB [Ora] is a key-value database library implemented in C,optimized for scenarios where efficient data retrieval and minimal resourceusage are critical. It is particularly well-suited for lookup tables providingdata access and management through straightforward function-call APIs.Key-value databases like Berkeley DB utilize a dictionary data structure,where data is stored as a collection of key-value pairs. In contrast, relationaldatabases such as SQLite use a more complex structure involving tables withpredefined data types and relationships. While this model is powerful forcomplex queries and structured data, it can be more resource-intensive interms of memory and processing power. Berkeley DB’s key-value model, lowmemory footprint, and efficient data access capabilities make it an excellentchoice for embedded systems, IoT devices, and other applications whereresources are constrained and performance is paramount. As an example,another 32-bit processor (S3C2410A) [Sama] has been used to port BerkeleyDB database. The device is 32-bit ARM920T RISC Microcontroller capableof running at speeds of up to 266 MHz and addressing up to 64 MiBytes ofNAND flash memory and 64 Mibytes of SDRAM.2.6.3 McObject eXtremeDBeXtremeDB [eXtb] is an ultra-small footprint, in-memory database sys-tem (IMDS) designed for embedded systems such as set-network routers,top boxes, telecom equipment, consumer appliances and other connectedequipment. eXtremeDB minimizes resource consumption and offers un-matched performance, reliability and development flexibility. eCosCentric[eXta] has ported eXtremeDB to STMicroelectronics STM32 processor. TheSTM32F405 [DS8] is based on the high-performance ARM Cortex-M4 32-bitRISC core operating at a frequency of up to 168 MHz. The STM32F405incorporates high-speed embedded memories (Flash memory up to 1 Mbyte,192.6. EMBEDDED DATABASESup to 192 Kbytes of SRAM), up to four Kbytes of backup SRAM, and anextensive range of enhanced I/Os and peripherals. ECoscentric extremeDBruns on an eCos operating system. eCos is an open-source real-time oper-ating system (RTOS) [eCo].2.6.4 ITTIA DB SQL embeddedITTIA DB SQL [ITT] is a relational database management softwarelibrary for embedded systems and Internet-of-Things devices. It runs onoperating systems such as Windows, Linux QNX, µcOS-II, µcOS-III, andVxWorks, and with a custom file system without an operating system. IT-TIA DB SQL is cross-platform and applications embedded with it run onARM Cortex-A, ARM Cortex-M, PowerPC, x86 and custom hardware plat-forms including AVR chips and Microchip® microcontrollers. By combiningSQL queries with low-level access to tables and indexes, ITTIA offers a setof database libraries that could be ported to run on a simple file system.2.6.5 AntelopeAntelope [TD11a] is a relational database management system deployedon top of the Coffee file system [Cof]. Antelope was designed for resource-constrained applications such as a sensor network system where every sensorholds a database. The database can be queried remotely or locally usingan SQL-like Antelope Query Language (AQL) without the complex SQLprocedures, triggers and transactions.2.6.6 LittleDLittleD [DL14] is a database application programming interface (API)used to interpret SQL statements. LittleD is a collection of C functionsdesigned to execute SQL statements on embedded devices such as the Ar-duino. The implementation of LittleD adapts to memory and code sizerestrictions by streamlining query parsing and execution and implement-ing efficient memory management techniques. Experimental results demon-strated that LittleD executes queries with joins and selections on deviceswith less than 2 KB memory in a few seconds.202.7. INDEXING SCHEMES ON FLASH MEMORY2.7 Indexing Schemes on Flash MemoryStorage and retrieval of data efficiently are the main tasks of a DBMS. Al-though various index structures have been used with traditional disk-basedDBMSs, they pose serious performance problems for flash-based databasesdue to the storage constraints. For instance, the B+tree, one of the mostcommonly used indexes in disk-based DBMS and file systems, consists of ahierarchical structure of data and provides efficient operations to find, delete,insert, and traverse the data. The basic way to implement a B+tree on flash-based memory is to use each page as a node for storing keys and records.However, since B+tree internal nodes only store keys and pointers and leafnodes store records; when an update occurs on a record in the leaf node, themodified leaf node needs to be written to a new page (in an erased block).Since the physical location of the node has changed, the pointer in the parentnode also needs to be modified, which requires another flash write opera-tion, again to a new page (in an erased block). This process continues untilall the nodes from leaf to root are written into flash memory [EM05]. Thisimplementation generates as many write operations as the height of B+treewhenever a single record is updated. This is obviously time-consuming, in-efficient and detrimental to the memory lifespan. Even when this processis implemented on FTL-based devices, small random writes are slow andquickly deplete the storage space resulting in frequent garbage collection.Consequently, flash-aware data structures and algorithms have surfaced toaddress this issue. Flash-aware indexing can be categorized into two majorgroups: FTL-based indexes which rely on the storage device FTL firmwareto provide a block interface to the storage, garbage collection, and wear lev-eling. The second group of indexes, known as raw flash indexes, is usuallyoptimized for small raw flash memories with the added task of handling thestorage wear leveling, garbage collection and page allocation. This sectionprovides an overview of some of these techniques and their implementationon flash-based database systems2.7.1 FTL-based B-treesB-tree for flash memory BFTLAdapting the B-tree to flash-based systems has been the subject of manyrecent attempts [WKC07b, LZYK+06, BHH07]. The authors of [WCK04]proposed a B-tree index management system for block-based flash storagesystems called BFTL. BFTL is a B-tree implementation residing over theFTL of a flash storage device. To reduce the extensive write operations212.7. INDEXING SCHEMES ON FLASH MEMORYgenerated by the transactions, a log buffer is introduced to record updatesto the index. BFTL consists of a memory write buffer called the reservationbuffer and a node translation table. When a transaction such as insert,delete, or update is executed, the newly generated records are temporarilystored in the reservation buffer. When the buffer is full, the records shouldbe written to a flash memory page. BFTL first generates the index units.These index units are packed into a single page and written to a flash memorypage. A node translation table keeps track of scattered index units. The nodetranslation table is similar to the FTL Logical/Physical mapping.Ftree Flash memory based treeTo reduce the number of writes in BFTL, Ftree was introduced [BHH07].Ftree uses B+tree instead of B-tree. B+tree is a more efficient indexingscheme for flash-based database systems because, unlike B-tree, B+treestores index entries in internal nodes and data entries in leaf nodes. Thus,B+tree is able to search more quickly with less I/O than B-tree. In F-tree,BFTL Index units are compressed before being packed and written to flashmemory. Additionally, F-tree exploits the over-write (one-way rewrite) op-eration to reduce the overhead of the write operation and reduces both thenumber of writes and the number of block erases over time. One-way writeis a feature of flash-based memory cells. To change the cell bit from 0 to1 an erase operation should be performed before the actual change. How-ever, to change the bit from 1 to 0, flash memory could perform the re-writeoperation without the need to perform an erase operation.Flash DBThe authors of FlashDB [NK07] distinguished two types of B+tree im-plementations. Disk-based implementation relies on the use of the FTL tomimic disk operations on flash storage. This allows for the existing imple-mentation of B+tree to run on flash-based storage. The drawback is thatupdates are very expensive. This type of implementation is more suitablefor applications with more read than update workloads.In log-based implementation, inspired by log-structured file systems, theindex is organized as transaction logs. A write operation on a B+tree nodeis encoded as a log entry and is placed in an in-memory log buffer. Whenthe buffer contains enough data to fill a page, it is written to flash. Anotherin-memory data structure (Node Translation Table (NTT)) maintains, foreach node, a linked list of page addresses where log entries for the node222.7. INDEXING SCHEMES ON FLASH MEMORYare stored on the flash. This type of implementation is more suitable forapplications with more updates than read workloads.FlashDB implements a self-tuning B+tree index based on workload andtype of storage. B+- tree (Log) is optimized for write-intensive workloads(e.g., where data is queried rarely) and for devices where writes are sig-nificantly more expensive than reads (e.g., SD card) because B+tree (Log)reduces flash writes at the cost of increased flash reads.Bw-TreeThe Bw-Tree [LLS13, WPL+18] was developed by Microsoft Researchfor use in SQL Server’s Hekaton main memory database engine. Its key fea-ture was its lock-free implementation enabling high concurrency when usedin main memory data processing. The implementation relied on a logicalidentifier to physical page address mapping table, where all pointer refer-ences were logical references that were translated to their physical memorylocations when required. This address translation indirection layer was sim-ilar to the node translation table used by BFTL but much more general asit applied to all pointer references. The authors noted the benefit of us-ing the translation table when storing on flash memory to resolve the writeamplification issue. The storage was log structured, so whenever a pagewas changed it was written to the next sequential location in storage. Themapping table allowed for no changes to the rest of the index as only thephysical address needed to be updated in the mapping table rather thanchanging the pages that contained the pointer reference. A key challenge isimplementing the mapping table itself as it is central to the approach. Formain memory databases on server systems, the most efficient implementa-tion was an array of physical pointers indexed by logical ID. However, thatimplementation would not be practical for an embedded system as a tablestoring all possible logical ID to physical page mappings could not be mem-ory resident due to the limited memory available. There were no extensionsto the Bw-Tree approach adapting it to embedded databases.2.7.2 Raw Flash B-tree variantsWandering TreeWandering trees [EM05] allow tree updates with out-of-place writes.When an update occurs on a record in the leaf node, the modified leafnode is written to a new page (in an erased block). Since the physical loca-tion of the node has changed, the pointer in the parent node also needs to232.7. INDEXING SCHEMES ON FLASH MEMORYFigure 2.8: Wandering Treebe modified, which requires another flash write operation, again to a newpage (in an erased block). This process continues until all the nodes fromleaf to root are written into flash memory. Figure 2.8 shows an example ofa six nodes tree (N1-N6) update, when N6 is updated its new version n6 iswritten to a new page and so are the new versions n3 and n1 of the parentnodes N3 and N1. The update of a single node resulted in three (height ofthe tree) writes. Hence, a single update will trigger O(h) write operations,where h is the height of the tree, triggering more frequent space reclamationand wear leveling.µ-treeµ-tree [KJKK07] was designed to address the inefficiency of wanderingtrees. While µ-tree is a balanced search tree like the B+tree, µ-tree storesall the nodes along the path from root to leaf into a single storage page.However, since the page size is fixed the size of each node is designed tovary depending on the level of the node and the height of the tree. The leafnode occupies half of the page, the remaining half is split among the nodesin the leaf-to-root path. Figure 2.9 depicts the example of a six node tree(N1-N6) update. When node N6 is updated both N3 and N1 are updatedand their new versions n6, n3 and n1 are stored in a single page. A singlewrite is therefore triggered when a leaf node is updated compared to theO(h) writes in the case of wandering trees.242.7. INDEXING SCHEMES ON FLASH MEMORYFigure 2.9: µ-Tree Update ExampleLA-treeLazy Adaptive tree (LA-tree) [AGS+09] is a balanced tree similar toB+tree, however, LA-tree introduces flash-resident buffers to hold updates.These buffers are associated with nodes at every alternate level, startingfrom the root. In Figure 2.10 buffer N1 is associated with the root nodeN1 and its descendants while Buffer Nj and Buffer Nk are associated withnodes Nj and Nk and their descendants respectively. Each buffer storesupdate operations of the corresponding node and its children. Hence allupdates are first appended to the root buffer N1, when the buffer overflows,it is read to memory, its entries sorted and batch pushed to the buffers in thelower levels and so on until the leaf node is reached. During lookup, the LA-tree performs a top-down search of the tree and the buffers attached to thenodes to account for updates that have yet to be committed to leaf nodes.Lookup time is increased compared to B+tree because of the additionalbuffer searches, however, the write operations are reduced as, depending onthe size of the buffers, most are replaced with append operations instead.252.7. INDEXING SCHEMES ON FLASH MEMORYFigure 2.10: Lazy Adaptive TreeIPL B+treeIn-page logging [LM07] divides the flash memory erase unit (block) intotwo regions to store both the Data Pages and Log Pages as shown in Figure2.11. Whenever updates are initiated to a page, the changes are loggedto the log region similar to a log-structured file system. The data pageitself remains intact. The page is first read to the in-memory buffer whereevery change is then written to the in-memory log area. The number oflog records on each page is proportional to the number of updates. Whenthe in-memory log area is full, it is flashed to the corresponding log area inthe flash memory. When the log area in the flash memory block is full, thepage is reconstructed and moved to a new erased block. To reconstruct apage, the original page in the data region and all its log records in the logregion are read and merged. IPL B+tree improves overall performance byfavouring reads over writes.2.7.3 Linear HashingLinear hashing has potential for embedded, flash indexing due to itsconstant time performance and minimal memory usage. Linear hashingwas developed by Litwin [Lit80] and expanded by Larson in [Lar82a] and[Lar82b]. Linear hashing is an expandable hash table with constant timeoperations. Linear hashing has been implemented in many database systemsincluding PostgreSQL. Even though B+trees are more commonly used, lin-ear hashing is interesting for flash memory as it has the potential to perform262.7. INDEXING SCHEMES ON FLASH MEMORYFigure 2.11: In-Page Logging Architecturefewer writes and its usage of random reads has no penalty in flash memory.It does not require a directory structure for finding bucket locations if buck-ets are allocated contiguously in storage. The hash table has the capabilityof dynamically growing or shrinking as the storage utilization (load factor)changes. Collisions are handled by using overflow chains. If the bucketwhere a record should be placed has no more space, a new block on storageis allocated to place the record and then this block is linked to the bucket.Thus, each bucket consists of a linked list of blocks on storage. Ideally, thenumber of blocks in each bucket is small if the records are distributed evenlywithin the hash table.The key feature of a linear hash table is that expansion occurs one bucketat a time instead of doubling the table size as in a regular hash table. Thisis made possible by the hashing function and splitting mechanism.H0(H) = H mod (N × 2L) (2.1)H1(H) = H mod (N × 2L+1) (2.2)Two hashing functions are used to calculate the table index shown in(2.1) and (2.2). These equations require the hash table properties N as theinitial number of buckets, and L is the number of times the hash table hasdoubled in size. Algorithm 1 is used to calculate the table index for a givenkey hash. In this algorithm, nextSplit is the next bucket that will be split.This algorithm finds the last number of bits in the key hash that is a valid272.7. INDEXING SCHEMES ON FLASH MEMORYFigure 2.12: Example linear hash table with hash keyshash table index. Every time the linear hash table doubles in size additionalbits in the hash are used to find the table index.Algorithm 1: Hashes a key to a table index1: Input: The key to hash2: Output: The table index where that key should be found3:4: function getIndex(key)5: hash ← SDBM(key)6: index ← H0(hash)7: if index > nextSplit then index ← H1(hash)8: end function9:10: function H0(hash)11: return hash & (initialSize - 1)12: end function13:14: function H1(hash)15: return hash & (2 × initialSize - 1)16: end functionOverflows in a bucket are handled by adding a new bucket to a linked listof buckets. Overflow buckets are chained together as needed. An exampletable is shown in Figure 2.12. This figure shows hashed keys inserted intoa table with an initial size of 4. This table demonstrates key hashing andoverflow chaining.The hash table is dynamically resized when the storage utilization (loadfactor) increases beyond a set amount. At that point, a new bucket is addedto the end of the hash file and records are divided between the new bucket282.7. INDEXING SCHEMES ON FLASH MEMORYFigure 2.13: Example of linear hash table with hash keys after a splitand the current bucket to split in the table.load = totalRecords/size ∗ recordsPerBucket (2.3)After every insert operation, load factor is calculated using (2.3) andcompared against the maximum load factor. If it is exceeded then a splitoperation is triggered.During a split operation, the table size is expanded by one and a newbucket is created. The bucket referenced by the nextSplit is loaded andsplit into the newly added bucket. Due to the way the hashing works, allrecords that should belong in the new table index are inside the buckets atthe nextSplit index.Records are moved if the H0 and H1 functions have different values.Once the split has been completed, if the table size has now doubled, thenextSplit is reset to the first index, otherwise, it is incremented by one. Anexample split is shown in Figure 2.13. In this example, a new bucket wasadded to the end of the table and records from table index 0 were split withthis new bucket.Linear hash Evaluation using Microchip SPIFlashLinear hashing was evaluated [FOM+19] on raw flash memory using anArduino Mega 2560 processor with 8 KB and SRAM running at 16 MHz.The Arduino is interfaced to a Microchip 64 Mbit SPIFlash SSTV26VFchip. This NOR Flash chip is based on Microchip®’s Super-Flash tech-nology which uses less current to program and has a shorter erase time(Sector/Block Erase: 18 ms (typ), 25 ms (max) Chip Erase: 35 ms (typ),50 ms (max)). The write size is 256 bytes, and the erase granularity is a 4KB sector. The data was obtained using the standard SPI interface.The performance of this memory is reading at 2.06 ms/block and writingat 3.95 ms/block. Reading is about twice as fast as writing (not consideringerase time). These times are similar to the read/write performance for theSD card experiments with reading being slightly faster. In both cases, thecost of transmitting the data from the processor to the memory using the SPI292.7. INDEXING SCHEMES ON FLASH MEMORYinterface is a bottleneck in the process. Implementing an algorithm on rawmemory chips has additional challenges as there is no flash translation layermapping logical file blocks to physical blocks in memory. The file-based andbucket map linear hash implementations that used a file interface for writingbuckets are not directly portable to this platform as that would require aflash translation layer. The sequential writing algorithm was adaptable toraw flash memory as the writes are occurring sequentially with no overwritesin the logical address space. A flash translation layer is not required, and thealgorithm must only manage when to cycle back to the start of the addressspace and erase blocks that were previously used. The performance resultswere about 6.3 ms/insert and 2.8 ms/get. These results are comparable withthe SD card performance but were only achieved by using the sequentialwriting algorithm that had extremely poor performance on an SD card.2.7.4 Sequential and Specialized IndexesMicrohashMicroHash manages data that has a timestamp when the sensor data wascaptured and a fixed-format record (a single-valued data record representingenvironmental parameters e.g. temperature). When data is captured fromthe environment, an index entry is created that points to the respectivedata stored in the flash memory (the authors refer to this as the growingphase) [LZYK+06]. When a node needs to evaluate some query, it uses indexrecords to quickly locate the data. MicroHash supports three main queries:value-based queries, time-based equality and range queries. MicroHash hasa sequential data file intermixed with index pages. Each index page storesindex records for a particular data value. The minimum memory require-ment for MicroHash is 6 pages (write buffer for data, write buffer for index,2 read buffers (index and data), buffer for directory index, and buffer forroot block). MicroHash also uses buffers for caching index pages.The MicroHash index size varies between 10% and 50% of the data sizeand depends on the size of the data records, the variability in the data, andthe amount of memory available to cache index blocks. By intermixing datapages and index pages, a modified binary search was required in MicroHash,which on average required about 5 reads for the data sets tested. Further,the index consumed more space as the index records are larger and cannotalways completely fill the pages. This is due to MicroHash using in-memoryhash partitioning of the data values in the index and being forced to flushan index page to storage whenever space must be freed up.302.7. INDEXING SCHEMES ON FLASH MEMORYAntelopeAntelope [TD11a] is a relational database management system deployedon top of the Coffee file system [Cof]. Antelope was designed for resource-constrained applications such as a sensor network system where every sensorholds a database. The database can be queried remotely or locally using anSQL-like Antelope Query Language (AQL). The inline index stores datarecords in increasing order by timestamp. Searching by timestamp used bi-nary search, but searching by value is not supported. The minimum memoryis 2 pages (one write buffer for data records and one read buffer for queries).This index structure has low overhead but does not also support efficientvalue queries [TD11b].PBFilterPBFilter writes data and index pages sequentially and uses Bloom fil-ters and bitmaps for data summaries. PBFilter requires at least 4 memorybuffers and has more writes as it has both a record-level index and indexsummaries. The index size consists of the space used to store an index entryfor each data record (where I is number of index entries that fit in a page)plus space used to store the summary of each data page (where F is numberof Bloom filters that fit in a page). Given that an index record size may benear the same size as a data record (i.e. 12 bytes), the index size may be aslarge as the data size. PBFilter does not discuss timestamp-based querieson the data file, but given that the data is written sequentially binary searchis possible. Value queries require reading the summary index and then anymatching data pages.IonDBIonDB is a key-value database designed for devices with limited storageand main memory. A variety of implementations have been deployed ontop of a file system such as FAT16 using SD cards [FHD+15]. Using a filesystem and a file translation layer to manage the storage device insulatesthe designer from having to manage the NAND Flash erase-before-write andblock wear (endurance) constraints. While the use of FTL-based storagedevice simplifies storage management, they add another layer of complexityby reducing available memory for buffering read/write operations.31Chapter 3Research SummaryThis research studies both sequential and random indexing on resource-constrained embedded devices. Sequential indexing includes techniques forindexing time series such as sequential binary indexing for time series (SBITS)[FOL21] and its evaluation comparison with other systems.Indexing data that appears random (not in sorted order) is studied byadapting B-trees to the low-memory embedded environment. The first B-tree implementation [OFL21] relies on a file system and storage such as SDcard, but has the lowest memory usage of any B+tree implementation.This B-tree research is expanded to produce VMtree, containing tech-niques for implementing the B+tree on raw memory including virtual ref-erences and log buffering. The resulting implementation has high perfor-mance on raw memory where no previous implementations exist for smallembedded devices and competitive performance with the prior implementedB+tree designed for SD cards.Overall, this research contributes by producing multiple different indexstructures, optimized for different storage and both sequential and randomindexing, on embedded devices.3.1 Embedded System EnvironmentThere are a wide variety of embedded devices. The small embeddeddevices targeted in this work have the following properties:− Memory-constrained (4 KB to 128 KB)− Flash memory storage (may be NOR or NAND)− May have either raw or FTL-based memory− Flash memory may support page-level overwriting and/or byte-leveldirect reads.323.2. RESEARCH OUTCOMESAs the indexes are deployed on embedded devices that have well-knownusage patterns, the embedded environment characteristics are known andavailable to the algorithm including:− The number of sensors and the frequency of sensor measurements− The size of the flash memory available to be used and its characteristics− The data processing requirements including queries, sliding windowaggregation, and consistency requirements− Append only data with increasing timestampsFor consistency requirements, the system must support both page leveland record level consistency. The types of queries supported include:− Equality and range timestamp queries− Equality and range value queries (but may be restricted to certainvalue ranges of interest)3.2 Research OutcomesMy initial work in the embedded indexing area focused on adaptingthe linear hash data structure [Lit80] for use on embedded devices. Thisincluded evaluating the performance of hashing algorithms on embeddeddevices [FOKFL18]. Hashing algorithms are important for data structuresinvolving hash operations. The linear hash data structure was adaptedto flash memory and evaluated on embedded devices [FOM+19]. For thisresearch, an embedded platform allowing direct memory writes with no flashtranslation layer was developed and evaluated in comparison to the standardapproach of using SD cards and the FAT-16 file system on Arduinos. Theresults showed that there is significant potential to adapt algorithms suchas hashing to use raw memory chips and not rely on a FTL or file system.The sequential indexing algorithm, SBITS [FOL21], was developed tohandle the key task of efficient time series indexing where the time seriestimestamp is strictly increasing. SBITS was compared against sequentialB-trees, sorted files, and hashing approaches and demonstrated superiorperformance [FOL21, OKFL22]. SBITS is currently the highest-performingembedded sequential indexing technique for small embedded devices. SBITSand its performance evaluation are covered in Chapter 4.333.2. RESEARCH OUTCOMESAlthough SBITS excels at indexing sorted, sequential data, there areoften use cases where the data is inserted randomly. The B+tree algo-rithm was adapted to use low memory on embedded devices that supportedfile-based storage [OFL21]. This B+tree implementation and evaluation isdescribed in Chapter 5.To improve performance on a wide variety of storage types, the B+treeimplementation was extended and enhanced to support B+trees on rawmemory such as NOR and NAND flash. The VMtree was developed thatis a B+tree supporting multiple storage types with specific optimizationsfor raw flash memory. VMtree utilizes virtual mappings to eliminate writeamplification and ensure high performance. VMtree is also optimized formemory that supports hardware-level overwrites [OKFL20]. VMtree allowssuperior B+tree performance on small embedded devices with many stor-age types. The VMtree implementation is in Chapter 6, and the extensiveexperimental evaluation on multiple hardware platforms is in Chapter 7.34Chapter 4Indexing Sequential DataPrefaceThis chapter is adapted from the published work in [FOL21, OKFL22].4.1 Problem DefinitionAn embedded device performs a fixed set of data operations, unlike ageneral database server. When the device is designed and deployed, thesedata processing operations will be known and implemented in the code base.By exploiting this knowledge, it is possible to build more implementation-specific optimized index structures.The data set is an append-only time series where each entry consists ofa timestamp and one or more sensor values. A sensor value is produced byreading from a sensor connected to the embedded device and is an integerof size between 8 and 32 bits. When reading using an analog-to-digitalconverter, the raw sensor value is then converted into an actual value basedon a sensor-specific transfer function. In many cases, the value producedis a floating point value. Processing and storing floating point values onmany small embedded devices increases device overhead due to architecturallimitations. Using the value in its discrete raw form instead of the convertedvalue is more efficient.These requirements are reasonable given that sensor devices are devel-oped, configured, and deployed with specific use cases and require efficientand reliable operation for extended periods of time.Embedded indexing has two key differences compared to indexing onservers. The first difference is the low amount of memory and CPU resources.Index algorithms must bound their memory consumption to execute in thisenvironment. The second difference is that embedded devices have specificoperational goals compared to more general indexing required for servers.For instance, an embedded device will have a specific data set it collects anddoes not generally have to respond to ad hoc or user-based queries. This354.1. PROBLEM DEFINITIONrestricted operational domain allows for optimizing and customizing indexstructures.Time series are the most common data collected by an embedded de-vice [SDO18]. Time series data may be environmental data (temperature,humidity, etc.) or operational data for sensors connected to machinery orelectronics. A time series data set consists of a set of records where eachrecord has a timestamp and one or more data values collected at that times-tamp. The timestamp in time series data is always increasing. The timeseries data is referred to here as a sequentially ordered data set. Insertingdata in sorted order has a major impact on the indexing structure used andthe associated performance. Sequentially ordered data sets also occur insituations such as auto-generated, integer keys.Indexing a time series data set requires indexing both the timestamp(which is sequentially increasing) and the data values, which are not. Thedata values typically have a restricted domain as they are produced bysampling through a sensor. These sampled data values are often a 10-bit to16-bit integer before they are converted into a floating-point value.Figure 4.1 contains an example time series data set used to describe theindex approaches. Each record contains a timestamp measured in seconds asthe first field and a sensed integer value as the second field. The timestampstarts at 0 for illustration but would usually be a value in seconds since UTC.The range of the sensed data field is small (15 to 30), which is common forsensed data. The records are grouped into 6 data pages each with 4 records.Data pages are stored in memory that is treated as a circular storage.Figure 4.1: Example of A Periodically Sampled Time Series Data364.2. INDEXING APPROACHDiscussion of the embedded index techniques uses consistent notationsummarized in Table 4.1. The number of pages used to store data is de-noted by D, and the number of index pages by I. The index pages may beexpressed as percentage of the data size D to characterize the index over-head. The number of data records per page is Nd, and the number of indexrecords per page is Ni. The size of the memory available to the index is Mpages. The page read and write costs are denoted by R and W respectively.The following sections overview the embedded indexing approaches.Notation DefinitionD Data size in pagesI Index size in pagesNd Number of data records per pageNi Number of index records per pageM Memory pages for use by indexR Page read operation costW Page write operation costs Query selectivityTable 4.1: Index Parameters4.2 Indexing ApproachThe proposed indexing approach minimizes writes and memory usage. Theindex structure adapts to the known query requirements and optimizes forthe queries specifically required for a particular use case.4.2.1 Data Record StorageThe foundation of the approach is that time series data records are writ-ten sequentially in pages to flash. This is similar to MicroHash [ZYLK+05]except that all data pages are contiguous, and are not intermixed with indexpages.Storing data pages contiguously works regardless if the flash has an FTLor supports overwrites. If the flash memory has an FTL, then all writes arelogical writes and all physical allocations are hidden. If the flash does nothave an FTL, there are several implementation possibilities:− Page level consistency - buffer page in memory and only write out fullpages to flash374.2. INDEXING APPROACH− Record level consistency:– Overwrites supported - append record to end of page using over-writes– No overwrites supported - write page to free space at end of mem-ory region temporarily, when page is full, write to end of dataareaThe ability to store the data records in sequential order by timestampenables efficient timestamp searches and minimizes the number of writes.4.2.2 Design Optimized Value IndexingSupporting value based queries efficiently requires adding an index struc-ture on top of the raw data storage. Without an index, a query on a datavalue requires a sequential scan of all data pages.The design decision is to deploy indexes based on the types of queriesthat will be required by the embedded device application. Since the devicewill not be executing interactive queries, these queries are known duringdesign time. The queries generally fall in two categories:− Point and range outlier value detection - value ≥ V or value ≤ V forsome value V− Recent history sliding window aggregates - for the most recent T timeunits, return the average, max, min, or count of value(s)A key observation is that the integer values often have a limited domain(e.g. 10 bits) and demonstrate skew and temporal locality. For example,a sensor collecting temperature data will have the values change relativelyslowly with a regular trend.To support efficient aggregate queries, each data page header containsthe smallest and largest timestamp values, the count of the number ofrecords, the minimum and maximum values in the page, and the sum ofall values in the page. The page header also stores a small bitmap indexthat approximates the data distribution. The size of the bit vector is deter-mined based on design requirements. Each bit represents the presence of avalue in the particular range with ranges being user defined.An example page structure that uses 2 byte values is in Figure 4.2. Thepage structure used for any particular time series data set depends on thequeries that must be supported. The only required fields are the 4 byte page384.2. INDEXING APPROACHid and 2 byte count. The time series range, aggregate summary and bitmapare optional. The overhead is about 24 bytes or 4.5% of a 512 byte page.To support multiple different values, the aggregate summary and bitmap isrepeated for each value in the sensor record.Figure 4.2: SBITS Page Structure ID: 4 bytes Page ID, Start: 4 bytes UNIXsmallest timestamp value in seconds, End: 4 bytes UNIX Largest timestampvalue in seconds, Cnt: 2 bytes count of records in page, Max: 2 bytes Maxvalue in page , Min: 2 bytes Min value in page, Sum: 4 bytes sum of valuesin page, Bmap: 2 bytes Bitmap indexThe bitmap is designed based on query requirements. For example,consider a value range of 0 to 100. One possible bit vector may divide therange into 10 equal buckets (0-9, 10-19, ..., 90-100) and require 10 bits ofstorage. If the values of interest are not equally distributed, the bit vectorcan be defined to capture the data of most importance. For example, if theanalysis queries are looking for very small or very large data values, it maybe better to use only 4 bits with the ranges (0-9, 10-49, 50-89, 90-100). Atthe limit, a single bit indicator can be used to determine a range of interest.For example, if the queries are focused on only values ≥ V , then 1 bit isused and is set only if the page contains values ≥ V .Database index tuning is commonly performed in database systems, butvarying an embedded index structure based on the required data analysisis unique. The bit vector filter in the header is configured based on designspecifications and only requires some additional space in each page. Noadditional I/Os are required. However, by itself, the bit vector does notsignificantly improve query performance or reduce I/Os, unless direct bytereads are supported, the system still must read the entire page from flash(although the bit vector does save time in processing records in the pageonce it is read).The bit vector for each page is also written out to an index area in aseparate area of the flash memory. Thus, index pages will not be intermixedwith data pages. One buffer is used to store the latest index page, and itis only written out when full. Given that a typical bit vector size per pageis between 4 and 16 bits, for a 512 byte page, the index size overhead andadditional I/Os is between 0.1 and 0.4%.394.2. INDEXING APPROACH4.2.3 Querying by TimestampThe pages are ordered by timestamp, and any timestamp can be retrievedin O(1) reads by calculating an offset using the start timestamp, the querytimestamp, and the rate at which records are written to flash (based onsampling rate and number of records/block). A given query timestamp tqcan be located by calculating its page index:page index = (tq − ts) ∗ rB(4.1)The first timestamp value is ts, and r is the sampling rate in records/sec-ond with B as the number of records/page. The page index is converted toa physical offset by multiplying by the page size in bytes.Since the memory is treated as a circular storage, after the data fills thememory for the first time, it is necessary to wrap the offset value based onthe current physical offset of the first data page in memory.For example, assume that the memory can store up to 100 data pages,and the data has wrapped around such that the current first data page is atoffset 50. If the page index is calculated as 75, then the physical page offsetis (50 + 75) mod 100 = 25.4.2.4 Querying by ValueFor queries by value of the form v1 ≤ value ≤ v2, query performance de-pends on the selectivity of the query predicate, s, and the ability to capturethat selectivity in the bitmap index. Every index-based query must read theentire index, which costs approximately 0.001 ∗ N where N is the numberof data pages. This is a sequential read and requires only one buffer for thecurrent index page.If the query predicate selectivity is s, then on average s ∗N data pageswill be read to process the query. The actual number of page reads dependson how the records matching the query predicate are distributed across thepages. If the query predicate exactly aligns with the bitmap vector such thatno false positives are generated, then the algorithm will read the minimumnumber of data pages required and is optimal. Since the indexes can beconstructed to support specific queries, it is possible to get perfect matchingand no false positives subject to space limitations. The algorithm for indexquerying by value is in Figure 4.3.When comparing the index and query bitmap, the two bit vectors canbe combined with logical AND, and any value greater than 0 (i.e. any bitset) indicates that the data page should be read.404.2. INDEXING APPROACHConvert query predicate into query bitmapLet P = 0 be the current data page indexfor each index pagefor each index recordif index bitmap AND query bitmap > 0read data page for this index recordfor each record in data pageoutput record if predicate is trueFigure 4.3: Querying by Value RangeThe overall cost of the algorithm is the cost to read the index pages andany data pages that contain records that match the predicate. If the bitmapindex supports the query predicate precisely, the minimum number of datapages, s ∗N , are read.As an example, consider a query for value >= 90. In the previoussection, two possible bitmaps were defined one with 10 bits and the otherwith 4 bits. In either case, the last bit in the vector, matches the predicateexactly, and only pages with records that match the predicate will be read.On the other hand, if the query is 25 ≤ value ≤ 75, then both bitmapswill return false positives. The 10 bit vector will have fewer false positivesas its value ranges have finer granularity and better overlap with the querypredicate.The other common query is sliding window summaries. The page-levelaggregate summaries support aggregate calculations without processing thedata records, and the filtering of rows by examining the minimum and max-imum data range. Using the header summary is especially useful if thememory supports byte level or partial page reads so only the header infor-mation is read rather than the entire page.In most use cases, the query will not scan the entire data set but only thelast few pages which represent the latest data in the sliding window. Givensufficient memory, previous data pages are obvious choices for buffering inRAM. If the number of pages in the sliding window is small, then it ismore efficient to read the pages rather than building another index of thesummary values.414.2. INDEXING APPROACH4.2.5 Memory ManagementThe minimum memory requirement is one write buffer for the currentdata page and a read buffer to read the data records. The addition ofthe bitmap index requires an additional write buffer for the index, and aread buffer when processing index queries. Any additional memory availablewould be used to buffer the most recent data pages, if the system uses slidingwindow queries on recent data. Thus, the minimum memory requirement is2 buffers without bitmap indexing and 4 buffers with bitmap indexing.4.2.6 Handling VariabilityDesign and operational parameters may change throughout the life ofan embedded sensor device. These changes include adding or removingsensors, modifying the frequency of sensor readings, and adapting the queriesperformed on the device.The approach easily handles changes in the sensors and their samplingfrequency. These changes only impact querying by timestamp, as timestamprecord locations are calculated based on sampling frequency and records perpage. These parameters are known at any given time, and if they changeduring run-time, the system must only store a history of previous values andthe time when the change occurred.For example, consider that the system has already stored 50 data pageswith the frequency r as 10 samples/hour and B = 10. If r is changed to20 samples/hour, then the system must record that starting at page offset50, r is 20. To calculate the page index for a time 120 hours from the firsttimestamp:page index = 50 ∗ 1010+ (120− 50) ∗ 2010= 190 (4.2)Thus, given knowledge of past sampling rates, calculating the page indexremains straightforward. Supporting different bit vector indexing strategiesis also possible by recording the page indexes when the bit vector structurewas changed.4.2.7 Wear LevelingWear leveling is performed by treating the memory as a circular arrayand wrapping around to the front of the memory region using a modifiedFrontier Advance Wear Leveling approach (FAWL) [FL11]. Figure 4.4 showsthe layout of memory for wear leveling. Pages are written to the location424.2. INDEXING APPROACHtracked by the page write frontier. In advance of the page write frontier, thesystem maintains a region of erased pages (write frontier extent) that allowspages to be written to the device. The temporary write extent is locatedin front of the write extent and is used as temporary record level storage.The size of the temporary write extent is a multiple of the memory device’sminimum erase unit and is aligned on a sector erase boundary. Generalsector erases are performed at the sweep frontier in front of the active dataextents.Figure 4.4: Frontier Advance Wear LevelingIf page level consistency is used, complete pages will be written to thepage at the page write frontier ( A○). The system assigns an increasing pageid to each page written (Pn) which is used to track the age of pages in thesystem. If record level consistency is being used, record updates will bewritten to pages (Tn) inside the temporary write extent at the record writefrontier ( B○). When enough records have been written to the temporarywrite extent to fill a page, the full page is then written to the page writefrontier.As pages are written to the system and the page write frontier advancestowards the temporary write extent boundary, the temporary write extentwill be advanced to the next sector of free pages. The system will erasethe sector tracked by the sweep frontier ( C○), advance the temporary writeextent and record write frontier to the position of the sweep frontier, and thesweep frontier will then be advanced to the next sector that will be targetedfor erase. The stale temporary write extent will then be erased. The writefrontier extent will then be updated to include this reclaimed area.As FAWL guarantees that the timestamp records are written to the mem-ory in a linearly increasing fashion, the sweep frontier will always reclaimthe oldest records in the system. Additionally, it wears memory uniformlyby writing and erasing sequentially, eliminating the need for a complex block434.3. ANALYSISwrite/erase management scheme or FTL.The system records the current page index for the start and end ofthe valid data pages. Preferably, this information is stored in non-volatilememory in case of system failure. Otherwise, it is recoverable by scanningthe memory. The first data page has the smallest page id, and the last datapage has the largest.4.3 AnalysisThe sequential bitmap indexing for time series technique, referred to asSBITS, is compared to other indexing approaches for embedded systems. Asummary of the approaches is in Table 4.3.Algorithm Index Size Min. MemorySBITS 0.004 ∗N 2 to 4Antelope index 0 2MicroHash 0.1 ∗N to 0.5 ∗N 6PBFilter B∗NI +NF 4B-tree B∗Nk 5Linear hash B∗NI 3Table 4.2: Comparative Analysis Size and Memory UsageAlgorithm Timestamp Query I/Os Value Query I/OsSBITS 1 0.004 ∗N + s ∗NAntelope index O(log2N) N/AMicroHash 5 0.1 ∗N + s ∗NPBFilter O(log2N)NF + s ∗NB-tree N/A O(logkN) + s ∗NLinear hash N/A O(1) (point query)Table 4.3: Comparative Analysis of I/OsThe inline index developed for Antelope stored data records in increas-ing order by timestamp. Searching by timestamp used binary search, butsearching by value is not supported. The minimum memory is 2 pages (onewrite buffer for data records and one read buffer for queries). This indexstructure has low overhead, but does not also support efficient value queries.The closest comparable strategy is MicroHash which has a sequentialdata file intermixed with index pages. Each index page stored index records444.3. ANALYSISfor a particular data value. The minimum memory requirement for Micro-Hash was 6 pages (write buffer for data, write buffer for index, 2 read buffers(index and data), buffer for directory index, and buffer for root block). Mi-croHash also uses buffers for caching index pages.The MicroHash index size varies between 10% and 50% of the data sizeand depends on the size of the data records, the variability in the data, andthe amount of memory available to cache index blocks. By intermixing datapages and index pages, a modified binary search was required in MicroHash,which on average required about 5 reads for the data sets tested. Further,the index consumed more space as the index records are larger and could notalways completely fill the pages. This is due to MicroHash using in-memoryhash partitioning of the data values in the index and being forced to flushan index page to storage whenever space must be freed up.The key difference and limitation of MicroHash compared to SBITS isthat index records based on offsets consume more space than the bitmapindex, and more importantly, good performance is only achievable if youcan buffer one page for each bucket in the hash table. If the hash tablehas 4 buckets, then that would require 4 in-memory buffers. In some datasets with low variability, it is possible to have fewer memory buffers, but thiscauses issues with only partially filled pages. The write cost using this indextechnique is considerably higher. When reading, more buffers are requiredfor range queries as each bucket that intersects the query range needs abuffer in order to make sure the data file is not read multiple times.PBFilter writes data and index pages sequentially and uses bloom fil-ters and bitmaps for data summaries. PBFilter requires at least 4 memorybuffers and has more writes as it has both a record-level index and indexsummaries. The index size consists of the space used to store an index entryfor each data record (where I is number of index entries that fit in a page)plus space used to store the summary of each data page (where F is numberof bloom filters that fit in a page). Given that an index record size may benear the same size as a data record (i.e. 12 bytes), the index size may be aslarge as the data size. PBFilter does not discuss timestamp-based querieson the data file, but given that the data is written sequentially binary searchis possible. Value queries require reading the summary index and then anymatching data pages. Compared to SBITS, PBFilter uses more memory andrequires more space and writes to maintain the index.B-tree implementations on embedded devices are restricted on RAM sotechniques based on extensive buffering are not applicable. A B+tree stor-age structure will allow for efficient queries on either the timestamp or valuebut not both. Assuming the data is stored sequentially by timestamp, then454.4. SEQUENTIAL INDEXING BENCHMARKINGthe B+tree is built on value. If the number of index records per page isk, search and insert is O(logkN). Buffers required are 2 for data (read andwrite) and 2 for B+tree (minimum of 2 for supporting split). To use anyform of log buffering, additional buffers are required. At a minimum, awrite buffer is required for log records. LSB-tree [KL15] is executable onmemory-constrained devices as it uses a single log area to support updatesand requires only one additional buffer for the log file. However, it gener-ates more writes and has costly re-organization operations to rebuild thetree periodically. Query performance and index size depend on k. B+treeimplementations are not optimized for append-only time series data.Linear hash implemented on embedded devices [FOM+19] supports key-based lookup in constant time. The minimum memory usage is 3 buffers,but better performance requires a buffer per hash partition otherwise everyinsert requires a page to be read from memory and then written with thenew data record. Timestamp-based queries and range queries on value arenot supported.Overall, the fundamental position taken is that the index structure canbe adapted at design time given that the queries to be supported will beknown in advance. With append-only time series data and known querypatterns, SBITS minimizes I/Os and energy usage by building the minimalpossible index to support the required queries. The number of writes isminimized, and the index size is less than 1% of the data size. Queries ontimestamp require only 1 read, and value queries will read the minimumamount of data if the bitmap index is tuned to match query predicates.4.4 Sequential Indexing BenchmarkingSequential FileThe simplest data indexing method is a sequential file. Each time seriesrecord is appended to the end of the sequential file as it is received. Bufferinga page of records before appending to the file improves performance.The advantage of a sequential file is its simplicity. Appending data isvery efficient and requires no data overwriting. Since the data is collectedin sequential order by timestamp, the sequential file is sorted by timestamp.Queries on timestamp can be performed in O(logD) using binary search.There are no index pages and no index overhead. Recovery is simple asthere is no data overwriting. It is also straightforward to delete old databy removing data from the start of the file. A sequential index structurewas implemented in the embedded database Antelope [TD11b]. The dis-464.4. SEQUENTIAL INDEXING BENCHMARKINGadvantage of sequential files is that searches on data value are O(D) andrequire a scan of the entire data file. Depending on the frequency of queriesand the size of the data set, this is a major performance issue. Many datalogging devices use sequential files due to their simplicity and portability.If the device performs only logging and timestamp queries and no queryprocessing involving data values, then sequential files offer the highest per-formance. The sequential data file requires two memory buffers. The writebuffer buffers records in memory until a page is full and then appends thepage to the end of the data file. The read buffer is used when reading datapages for queries.PartitioningRange or hash partitioning the data allows for faster search. Rangepartitioning separates the values into ranges with each range having a bucketfor storage. In hash partitioning, a hash function is computed on a value todetermine its partition index.MicroHash [ZYLK+05] was one of the earliest embedded indexing ap-proaches. The time series data was stored in a sequential data file and anindex built on top of it to allow for querying data values. MicroHash workswith raw flash memory or storage with a FTL such as SD cards. A designissue is that data pages were intermixed in the sequential file with indexpages with the goal of providing uniform memory wear. Unfortunately, in-termixing data and index pages complicates time series searches. Althoughvarious modifications were proposed, the performance is slower than binarysearch.A partitioning index allows for querying on data values. Despite thename MicroHash, the index was built using range partitioning (not hashpartitioning). The domain of the data value was divided into ranges thatcould be further subdivided if the number of values in a partition grewbeyond given bounds. When a record with a given data value was in apartition, the page number of the record was stored in the partition to allowfor fast retrieval.The performance of partitioning depends on the number of partitionsand the memory available. Figure 4.5 shows the partitioning of the exampledata set into 5 partitions for two memory sizes M = 3 and M = 5. In theM = 5 case, each partition has a buffer in memory. The partition indexcontains the ranges of each partition and a pointer to the first page of eachpartition. Within an index page, there is a page id record if the page containsat least one data value in that range. For example, partition index 2 has474.4. SEQUENTIAL INDEXING BENCHMARKINGFigure 4.5: Range Partitioning Exampleindex records to pages 1, 2, 3, and 5 as all have a value in the range 19 to21. With a buffer for each partition, one page per partition index remainsin memory and is only written to storage when completely full.The M = 3 case illustrates the challenges with range partitioning. Atmost 3 index pages can be memory resident at a time. When an indexpage is not currently in memory, the system must write an index page tostorage to free space. When processing data page 1, its data values are allin partition index 2. A buffer page is used for partition index 2 and the pageid 1 is added to the index page. When data page 2 is written, its values alsoare all in partition 2, so page id 2 is added to the index page. For data page3, a buffer is added for partition 1 and page id 3 inserted into the partitionindex. Page id 3 is also added to partition index 2 and 3. Page 3 also mustbe added to partition index 4, but there is no memory available. The indexpage for partition 1 is written to storage to provide space. Note that thisindex page has only one entry and has very poor space utilization. Datapage 4 requires partition 1, which is no longer in memory. Partition index 2is written to storage. The page for partition 1 is read into memory and theentry for page 4 is added. The previous page for partition 1 on storage isobsolete. Data page 5 requires partition 2, so partition index 3 is written tostorage. The page for partition 2 is read from storage and updated. Finally,data page 6 requires partition index 3 and 4 so partition indexes 1 and 2 arewritten to storage.A query for a given data value only must retrieve the pages that are inthe same partition as the data value. For example, if the query was for allrecords with data value 15, then only partition 1 needs to be read whichhas data pages 3 and 4. Consider a data file with 1000 data pages. Eachpartition record is a 4 byte integer page id, so we will assume Ni = 62records per 512 byte page. At minimum, the index size I is 16 pages ifeach page falls into only one partition. It is common that a page may have484.4. SEQUENTIAL INDEXING BENCHMARKINGdata values in multiple partitions so the page id would be inserted in eachpartition that it has a value in. Assume that 5 partitions are used. Then, toquery for all records with data value 15, partition 1 is read. Assuming datais uniformly distributed, partition 1 would have about 3 pages of index andhave page ids for 20% of data pages. Querying for all records with value 15requires about 3 index page reads plus 200 data page reads.The fundamental issue with partition based indexing is that the queryperformance depends on the number of partitions. With uniform data andDpages with P partitions, a query will read D/P data pages. Increasing queryperformance requires increasing the number of partitions. However, eachpartition requires a buffer in memory, and an embedded device is severelylimited on memory.MicroHash attempts to handle this issue by allowing more partitionsthan available memory buffers. This results in having to write out indexpages that are not full whenever a buffer is needed for an index page notcurrently in memory. Although techniques are presented to limit the is-sue of partially full index pages, the fundamental issue is always present.The effect is mitigated to a degree when data values are slowly changing(e.g. temperature) making the partitioning more linear rather than ran-dom. However, the example demonstrates how the index utilization andperformance drops dramatically if there are not enough memory buffers foreach partition and a data page has values that span multiple partitions. Itis possible to write multiple index pages for each data page written resultingin very low utilization and high query overhead.Hash partitioning has less application than range partitioning as it willdistribute values randomly across the partitions and does not support rangequeries that are common for embedded applications. Linear hashing hasbeen implemented for embedded systems [FOM+19], although the imple-mentation is not optimized for time series data and does not support rangequeries.Our partitioning implementation based on MicroHash uses range par-titioning with P partitions with the number of partitions and the rangescontrollable by the index user. When defining an index, a partitioning func-tion is supplied, written in C, that defines how to find a partition index foreach data value indexed. The default partitioning function equally dividesthe range of data values into equal sized partitions.The partitioning index is given M − 2 buffers (min. 1) with the othertwo buffers used for the sequential data file. If the number of partitions Pis larger than M − 2, the algorithm ensures that when a partition is neededit is in an in-memory buffer. If a partition in memory must be evicted to494.4. SEQUENTIAL INDEXING BENCHMARKINGfree up space, the partition buffer is written to its partition index if changeshave been made. When the partition buffer is required again, it is read fromstorage and updated.A summary of the partitioning algorithm is in Figure 4.6. Whenevera data page is appended to the data file, the partition index is updated.First, the data page is sorted on data value. Then, the records are scannedin sorted order, and for each data value its partition is determined. If thepartition for a data value is the same as the previous record, no updates areperformed. Otherwise, the page number of the data file is inserted into theproper partition. This repeats until all records in the page are processed.Note that a given page id may be in multiple partitions if it has data valuesthat fall in multiple partitions.write data page to sequential data filesort data page in memory buffer by data valuefor each record r in data page:if r is in different partition p than previous record:if partition p is not in memory:if no buffer space available:write out buffer for another partitionread current page for partition p into bufferadd record to partition with data page numberFigure 4.6: Partition Algorithm ImplementationFor data queries, the partition(s) of the data values are determined.Each partition is scanned one page at a time. An index page is read intomemory that contains page ids with values in that partition. Each data pageis then read and values output. The partitioning implementation uses thebest features of MicroHash with several optimizations. The key differenceis the separation of data and index pages that allows for faster timestampqueries. Another optimization is building the index after writing each datapage and sorting the records before determining partitions.TreesThe B-tree has O(logD) insert and query performance but performsrandom reads and writes. There have been numerous adaptations of B-trees for flash memory. Optimizations delay writes by buffering modifiednodes in memory and using log-based approaches to log changes to the treestructure rather than immediately updating. Buffering techniques includewrite-optimized trees [BFJ+15] that divide each page into a record area and504.4. SEQUENTIAL INDEXING BENCHMARKINGa modification area. When the modification area is full, updates are pusheddown to lower nodes in the tree.Approaches based on logging rely on logging modifications in either aseparate area of flash or on each page itself. One of the earliest flash B-treeimplementations [WKC07a] used a log area that stores changes to the tree.When the log area was full, changes to the tree were performed in batch.The approach requires sufficient memory to buffer the changes in the log aswell as a translation table for mapping pages to physical addresses. Log-structured merge trees (LSM-trees) [OCGO96] consist of multiple levels ofB-trees with the top-level buffered in memory. LSM-tree variants offer highwrite performance with a trade-off of lower read performance and a largeamount of memory consumed. The Always Sequential B-tree [RKLP14]uses buffering and writes updated pages sequentially to the end of the file.This avoids random writes but requires a logical mapping table as pagesreferencing an updated page are not updated themselves.B-tree implementations for flash memory and SSDs are not executableon memory-constrained embedded devices if they do not adapt to the lowmemory available. Techniques based on buffering and deferred writes havelimitations due to the limited memory that is available for buffering.Some B-tree implementations work on raw flash memory without anFTL. The In-Page Logging (IPL) technique [NLM12] uses logging areasassociated with each page co-located on the same block. Using the loggingarea reduces the writes but requires more reads and a periodic merge processcombining the log area into the tree structure. The Log-structured B-tree(LSB-tree) [KL15] used a log node for each leaf page and a mapping table tohandle mapping leaf nodes to log pages. A B-tree implementation [OFL21]for embedded devices that uses limited memory is available. For certainmemory types, it may be possible to perform partial page flash updates inrestricted cases [HKVP19].B-trees are an efficient general index structure, however, they are notspecifically optimized for time series data. A single B-tree cannot index boththe timestamp in the time series and the associated data values. Possibilitiesinclude using two B-trees, one for the timestamps as a primary index andone for the data values as a secondary index, or to use a sequential datafile storing the ordered timestamp records that is indexed on data valueusing a B-tree. The B-tree indexing data values must be capable of handleduplicates.Figure 4.7 contains a B-tree indexing on timestamp. Each leaf node isa data block that is ordered on timestamp. Each interior node provideskey values for navigating efficiently to a data block. In this case, a leaf514.4. SEQUENTIAL INDEXING BENCHMARKINGdata block contains up to 4 records, and each interior node contains up to 2keys. In practice, the number of keys in an interior node will be high. Forexample, with a 512 byte page and 4 byte key, each interior record (key andpointer) is 8 bytes and about 62 key/pointer pairs are stored in each page.This results in the height of the B-tree being small and any data page canbe found in about 3 to 4 page reads.Since the data is sorted by timestamp, building the B-tree index ontimestamp is very efficient and is similar to bulk index loading where the datais sorted before adding to the index. In this case, each data block written tothe data file is always completely full. An index entry is added to the nodeabove the leaf level. Each index node is filled completely before adding anew index node. This results in index utilization near 100% and no readsto insert a page of records into the index. Optimizing for sequential, sorteddata in an index has been used in various databases such as PostgreSQL.Figure 4.7: B-tree Primary Index on TimestampFigure 4.8 shows a secondary B-tree indexing on data value that refersto the primary index. Each index entry is a tuple consisting of the datavalue and the page where it is present. This resolves the duplicate valueissues in the B-tree. This index allows fast query by value to determine thepages where a given data value occurs. The index adds one entry per pageeven if a record occurs multiple times. Since page level I/O is performed,there is limited benefit to indexing each record individually and indexing bypage results in a smaller index size.Two distinct B-tree implementations are evaluated. The first imple-mentation is a sequential B-tree (sbtree) optimized for ordered data. Thesequential B-tree implementation can be used instead of a sequential datafile for storing the records sorted by timestamp. When inserting records,the sequential B-tree fills leaf and interior nodes completely and requires noreads to find the page to insert the record. The sequential B-tree has slightly524.4. SEQUENTIAL INDEXING BENCHMARKINGFigure 4.8: B-tree Secondary Index on Data Valuemore index overhead than a sequential file, but also guarantees O(logNiD)search performance. This is improvement over binary search as the numberof index records per page (Ni) is often between 50 and 100.A general B-tree implementation indexes the data values based on theB-tree implementation in [OFL21]. The implementation handles duplicatedata values by requiring that each key inserted into the tree consists of thepair (data value, page id) as shown in Figure 4.8. An insert operation re-quires searching for the leaf page to insert the record into and then insertingthe record. A record insert will modify the page which is overwritten iffile-based storage is used with flash memory that has a FTL (such as a SDcard). If no FTL is available and the memory does not support overwriting,then the modified page is written to the next sequential page in memoryand a mapping is added in a mapping table that converts old page addressto new page address. By using the mapping table, a page modification doesnot require updating other nodes in the tree with pointers to the page thatwas modified.Similar to the partitioning implementation, when a data page is writtento storage, the B-tree index is updated. The records in the data page aresorted, and B-tree records are added for each distinct data value in thepage. Another variant was produced that added an index record for eachdata record in the page. This variant results in a larger secondary index sizebut allows for answering data queries without reading the data file itself.The B-tree consumes one memory page for a write buffer. It also requiresat least one page for a read buffer. Additional memory buffers supplied areused to cache recently used pages. Given sufficient memory, the root nodeof the B-tree is always cached.When searching the time series by data value, the B-tree is used to findthe leaf node containing the data value. Since a data value may occur inmultiple pages, a scan of the B-tree leaf nodes is performed to retrieve allthe page ids that contain the data value. The pages will be returned in534.4. SEQUENTIAL INDEXING BENCHMARKINGsequential order as the B-tree sorts records by data value and page id.BitmapsBitmap indexes are common in data warehousing applications when in-dexing attributes with low cardinality. With a bitmap index, each potentialattribute value is assigned a bit in a bitmap. When scanning the data set,only records (or pages) that have the corresponding bits set are read duringthe query. A bitmap index is memory efficient as long as the domain is small.There is research on encoding [WSS08] and compression [WOS06, SWW+08]methods for bitmap indexes.PBFilter [YP12b] used a sequential data file for storing data records thatwas indexed using a memory efficient key index. The key index consisted ofBloom filters. PBFilter wrote to both the data file and index file sequen-tially. By using Bloom filters, the index overhead was small and querieswere efficient.SBITS [FOL21] is a sequential indexing scheme using a bitmap index.Both the data and index file are written to sequentially. Compared to PB-Filter, SBITS consumes less memory and the index size is smaller. SBITSwas designed for highly memory-constrained devices (4 KB to 128 KB RAM)and operation on either raw flash (NOR, NAND) or FTL-based storage (SDcard). A unique contribution in SBITS was adapting the index directly tothe embedded application. Given that embedded devices have highly con-strained operational requirements, it is advantageous to modify the indexfor a specific use case and deployment.The SBITS implementation buffers a page of records in memory andwrites full pages sequentially to flash. When a page is written, a bitmap isadded to the page header that summarizes the data values it contains. Thesize and construction of the bitmap is user-defined on index creation. Theuser supplies two functions: a bitmap check and a bitmap creation function.The bitmap check function takes a bitmap and a data value and returns trueif the data value is in the bitmap. The bitmap creation function takes anexisting bitmap and a new data value and updates the bitmap to include thenew data value. SBITS allows any bitmap related filter including succinctrange filters [ZLL+20].Figure 4.9 contains a bitmap index on the data value for the exampletime series. Instead of using a bit for each value in the domain (which issize 16 in the example data set), binning by ranges is used to assign a bitfor each range. Using binning requires only 5 bitmaps. Customizing thebinning and encoding strategy for the embedded use case can substantially544.4. SEQUENTIAL INDEXING BENCHMARKINGFigure 4.9: Bitmap Index on Time Series Data554.4. SEQUENTIAL INDEXING BENCHMARKINGimprove performance.The page bitmap is also written to an index file. For example usingFigure 4.9, when page 1 is written a bitmap of size 5 bits (01000) is writtenin the page header and to the index buffer. A page in the index buffercontains multiple bitmap index entries and the page id of the first pagereferenced by the first bitmap entry. When the index page buffer is full, it iswritten to the index file. The implementation requires one write buffer andone read buffer. After processing the 6 data pages, the index page contains6 bitmaps of size 5 bits.The default bitmap implementation uses bitmaps of size 64 bits andperforms range binning uniformly in the data range. Given a page size of512 bytes, each index page stores 62 entries with a 16 byte header. Theindex overhead is 1/64 or 1.6%. A 16 bit bitmap has overhead of 0.4%.When performing a data query using the bitmap, the data range queriedis mapped to a query bitmap. Only pages that overlap the query bitmapare read. For example, querying for the value 20 requires reading pages 1,2, 3, and 5 as the bitmap B1 is set for those pages. Note that binning byranges may result in false positives where the bitmap indicates a record inthat range exists in the page, but it may not directly overlap with the query.For example, querying for the value 16 would read pages 3 and 4, but onlypage 4 actually has a value for 16. Querying a range of values, such as 20to 25, requires processing multiple bitmaps (B1, B2, and B3), and readinga page if any bitmap has a 1.The algorithm for a data query is in Figure 4.10. SBITS reads each indexpage and processes each record. If the index record indicates a potentialoverlap of the data values with the query, then the data page is read andprocessed. SBITS will read all index pages and a number of data pagesbased on the query predicate selectivity s. The actual number of page readsdepends on how the records matching the query predicate are distributedacross the pages. If the query predicate exactly aligns with the bitmap vectorsuch that no false positives are generated, then the algorithm will read theminimum number of data pages required and is optimal. A bitmap indexcan be constructed to support specific queries and get perfect matching withno false positives.SBITS also implements an efficient timestamp search algorithm that isfaster than binary search. The approach uses an interpolation search usinga linear function that is determined based on the rate that records are in-serted and the number of records per page. For applications with a constantrecord insert rate (e.g. every 60 seconds), it is possible to precisely predictthe page location of a record based on its timestamp (O(1)). Variations564.4. SEQUENTIAL INDEXING BENCHMARKINGConvert query predicate into query bitmapLet P = 0 be the current data page indexfor each index pagefor each index recordif index bitmap AND query bitmap > 0read data page for this index recordfor each record in data pageoutput record if predicate is trueFigure 4.10: Querying by Value Rangeof sampling frequency are handled by recording different linear functionsfor certain timestamp ranges. This approach has characteristics similar tolearned indexes [FV20, MKvR+20] that construct models to predict a recordlocation in a sorted data set. Constructing the linear models for differenttime ranges is simple with no overhead. Future work may consider morecomplicated models which would be required if the time series show morevariation than can be handled using piece-wise linear models.SummaryIndexing on memory-constrained embedded devices can be performedusing sequential files as well as indexes based on partitioning, trees, andbitmap summaries. For insert-only workloads, sequential files are efficientto implement and have the highest performance. When queries are added tothe workload, sequential files have poor performance and an additional indexstructure has benefits. Partitioning improves query performance by dividingthe records into partitions such that only partitions related to the query needto be read. Partitioning is limited by the available memory and performancedecreases significantly if insufficient memory is available to buffer a page foreach partition. Trees have consistent O(logD) performance, but performrandom reads and writes. Indexing the time series data values requiresa B-tree to handle duplicates. If no FTL is available, the tree structuremust also handle page overwrites and memory management. SBITS bitmapindexes are very space efficient, and the bitmap approach used is flexible tobe optimized for particular use cases.574.5. THEORETICAL PERFORMANCE ANALYSIS4.5 Theoretical Performance AnalysisTable 4.4 contains a summary of the theoretical space and query perfor-mance for the embedded index implementations. The following parameterswere used with the model. The page size is 512 bytes. The key size is 4 bytes,and a page id (address) is 4 bytes. The bitmap index uses a 2 byte bitmapper page. Each page has a 12 byte header leaving 500 bytes of space fordata or index records. For the analysis, the data distribution is assumed tobe uniform, although performance will vary based on the data distributionin practice.Index Idx Size Buffers Key Query Data Querysequential file 0 2 log2D Dpartitioning 0.008 ∗D 3 + P log2D D/P + 0.008 ∗DB-tree 0.024 ∗D 5 logNiD s ∗D + logNiDSBITS 0.004 ∗D 4 O(1) s ∗D + 0.004 ∗DTable 4.4: Theoretical Index PerformanceThe sequential data file has no index overhead and requires the minimumamount of memory. Timestamp queries require a binary search on the datafile, and data value queries require a scan of the entire data file.Partitioning using P partitions requires 3 + P memory buffers, two forthe sequential data file, one for reading partitions, and the rest for bufferinga page per partition. Although it is possible to have less memory than this,the index size overhead and query performance will be negatively affected.Querying for a data value will read D/P pages with uniform data as well asthe partition index pages. The minimum index overhead is 0.8% assumingcompletely full index pages, and each data page has values in only onepartition. The index overhead could be an order of magnitude higher ifthese assumptions are not met.The B-tree uses 5 memory buffers (2 for primary data file, 1 write buffer,and at minimum 2 read buffers). If a primary index B-tree is used ontimestamp, the query performance is logNiD as each index page containsNi entries. Ni for the given parameters is 62, so the height of the treeis usually no more than 3 or 4. If using a secondary index B-tree and asequential data file, then the timestamp query is log2D (same as sequentialfile) and the data value query requires reading one page per height of tree(to find first leaf) then scanning other leaf nodes. s is the selectivity of thequery. It is the number of data pages that contain values in the requestedrange. The minimum index overhead is 2.4% assuming B-tree index nodes584.6. EXPERIMENTAL RESULTSare approximately 66% full.The SBITS bitmap approach uses 4 memory buffers (2 for sequentialdata file, 1 write index buffer, and 1 read index buffer). Using the page lo-cation prediction algorithm of SBITS, the bitmap index can retrieve a giventimestamp record usually in only one or two page reads. Its performance fordata value queries requires scanning the index pages (0.004∗D) then readingany matching data pages based on the query selectivity (s). It is possiblefor the bitmap to produce false positives and read more than the minimumdata pages depending on the bitmap binning and encoding technique used.The index overhead is 0.4%.Overall, there are several key differences between the approaches. SBITSis the most space efficient, which results in fewer writes when building theindex and reads when using it for queries. Partitioning may store a page idmultiple times that occupies more space. The B-tree stores key and page idrecords that require at least double the space, and potentially more for largerkey sizes. The performance of the B-tree for queries is consistent and maybe the fastest for large data sets. However, its index overhead is the highestand requires many random reads and writes to maintain. Partitioning suffersfrom a fundamental issue of high memory consumption to buffer partitionsthat affects performance.4.6 Experimental ResultsThe two hardware platforms selected for these experiments are repre-sentative of hardware used in time series data collection sensors. The firstplatform uses an 8-bit AVR® ATmega2560 microcontroller with 256 KB offlash program memory. This platform was selected due to its small mem-ory (8 KB of SRAM) and limited CPU performance (16 MHz clock speed).This is the processor found on the Arduino MEGA 2560 development plat-form and contains many common design elements found in applications. ASanDisk microSD card of 2 GB was used for storage attached with an Ar-duino Ethernet shield. The page size was 512 bytes. SD cards are typicallyused by developers for portability but also for convenience as they provide ablock-level interface to the storage using a built-in FTL. Programs can usefiles on a SD card similar to other file systems.The second hardware platform has a 32-bit Microchip® ARM® Cortex®M0+ based SAMD21 processor with a clock speed of 48 MHz, 256 KB offlash program memory and 32 KB of SRAM. The hardware board has sev-eral different memory types including an SD card and serial NOR DataFlash594.6. EXPERIMENTAL RESULTSReads (KB/s) Writes (KB/s)Device Seq Rnd Seq Rnd Read/Write RatioATmega2560(SD card)200 200 125 50 1.6 (seq), 4.0 (rnd)M0+ SAMD21(SD card)515 355 430 40 1.2 (seq), 8.9 (rnd)M0+ SAMD21(DataFlash)475 475 38 38 12.5Table 4.5: Hardware Performance Characteristics[SPI] which supports in-place page-level erase-before-write. This platformwas chosen as it represents devices with more capabilities and commonlyused 32-bit ARM processors. Although the device has more memory andCPU power, its cost is comparable to the ATmega2560. Two memory typeswere selected for data storage, an SD card, that represents a typical use casefor developers that want to simplify storage, and a raw NOR DataFlash totest performance on raw memory without an FTL. A summary of the per-formance characteristics of the hardware is in Table 4.5.For the DataFlash if erase before write is not used (i.e. pages were pre-erased), write performance was 320 KB/sec. Read and write performancewere measured by writing 1000 pages either randomly or sequentially andreading the pages either randomly or sequentially. Note the large differencefor the SD card sequential versus random write performance. This differenceis due both to the physical characteristics of the card as well as overheadof the FTL algorithm and the SDFat library used for accessing files. Per-formance on the DataFlash is consistent regardless if using sequential orrandom I/O. Reads are over 10 times faster on the DataFlash than writes.The experimental data set was the real-world data set used in Micro-Hash [ZYLK+05]. This environmental data set consists of temperature,humidity, and wind speed readings from various temperature stations inWashington[Liv]. The two stations used were located at the Universityof Washington (that sampled every minute) and at Sea-Tac airport (thatsampled every hour). The timestamp was converted into a 4-byte integerrepresenting a UNIX timestamp in seconds. The record size consisted of16 bytes total including a 4-byte timestamp, 4-byte temperature, 4-bytepressure, and 4-byte wind speed. Indexing was on the temperature value.All experiments are the average of 3 runs as there is almost no vari-ability in execution times. The memory allocated for the algorithms wasdetermined by finding the minimum memory requirement that provided the604.6. EXPERIMENTAL RESULTSbest performance. The memory used was SBITS (bitmap) (M = 4), parti-tioning (M = 5), sequential B-tree (M = 3), and B-tree (M = 6). On theATmega2560 device, it was not possible to have large values of M due tothe 8 KB of RAM and the SD card library using several KB of memory.4.6.1 Insert PerformanceInsert performance is critical as insert operations are the majority of op-erations performed by the embedded logging device. The one-minute sam-pling data was used, and the experiment evaluated inserting 100,000 records.The insert rate is shown in Figure 4.11 for the ATmega2560 platform.The sequential file has the highest performance. The SBITS bitmap ap-proach is about 10% slower although it performs only about 2% more I/Os.The computation of the bitmaps and managing the index file takes time onthe ATmega2560 as it has a slow clock speed. The sequential B-tree (sbtree)and partitioning approaches have roughly equivalent performance and about30% less inserts/second. Both of these techniques perform no random writesor reads. The two B-tree implementations, one indexing per record and theother per page, have an order of magnitude slower performance due to therandom reads and writes performed. It is important to note that even in thiscase, the inserts/second are 60 and 160 respectively on low-end hardware.This performance is more than adequate for devices that are sampling oncea minute. All techniques have a stable insert rate even as the number ofrecords inserted increases.Figure 4.11: Index Insert Performance on ATmega2560Additional data on the performance differences is in Table 4.6. Thisdata includes the additional I/Os performed compared to the sequential file614.6. EXPERIMENTAL RESULTSapproach. The I/O numbers are independent of hardware. The data file sizewas 3226 pages for the 100,000 records. Percentages are given with respectto this size. Thus, a percentage of 102% for sbtree writes corresponds to6504 writes (or double the amount required if storing just the data file itself).Metric SBITS partition sbtree B-tree B-tree (page)reads 0% 0% +102% +102% +102%index reads 0% +9% 0% +7009% +1376%writes 0% 0% +102% +102% +102%index writes +1.6% +10% 0% +3293% +1204%index size +1.6% +10% +1.6% +98% +35%Table 4.6: Index I/O Metrics for Insert Experiment - Percentage AdditionalI/Os Compared to Data File SizeThe SBITS I/O results exactly match the theoretical values. The indexsize and additional writes represent an overhead of 1.6% compared to thedata size. A 64-bit bitmap was used. The partitioning approach has goodperformance for the temperature data. The actual index overhead is 10%,which is higher than the theoretical minimum as data pages often havedata values that fall into multiple partitions. The number of partitions wasP = 10 with M = 5. Even though there was not enough memory to buffera page for each partition, overall the performance was still very good as theone-minute sampled temperature data changes slowly resulting in a datapage typically only having values in one or two partitions. These results areconsistent with the results for MicroHash [ZYLK+05].The partitioning performance is fragile and highly depends on the dataset. Using the temperature data set sampled every hour at Sea-Tac resultsin considerably different results. Each data page had data that was onaverage in 3.5 partitions. With M = 5, the algorithm was writing over 40times more index pages with less than 2% index page utilization. To havesimilar performance as the one minute data set, M = 11 is required, whichalmost allocates one page buffer per partition (M = 12 allocates one bufferper partition with 10 partitions as the other two memory buffers are usedfor the data file). Although for certain use cases it is possible to have lessmemory available than partitions, in general this is not a stable situation.The sequential B-tree has consistent, bounded performance and performsabout double the number of writes compared to writing to the sequentialfile. The additional writes occur as the path from root to leaf is not bufferedin memory. This results in at least one read and write of an index page624.6. EXPERIMENTAL RESULTSwhenever a completely full data page is written. The index overhead is1.6% as the number of index pages is low. The sequential B-tree is onlyindexing the timestamps in the time series, not the data values, so its in-dex performance is not directly comparable to the other approaches. Thesequential B-tree performance is included to demonstrate the overhead ofindexing only the timestamp using a B-tree structure and to provide somecontext with the B-tree indexing algorithm that uses a sequential B-tree toindex the timestamps and a general B-tree for indexing the data values.The insert performance of the two B-tree approaches (record-level andpage-level indexing) is over an order of magnitude slower than the otherapproaches due to the high number of random reads and writes performed.Whenever a data page is written to storage, one or more index entries areinserted into the data value index. Each index record inserted writes atleast one page and may write more if the B-tree index structure also requiresupdating. Unlike the sequential B-tree structure, these are random writes asthe insert page could be any leaf node due to the data values not appearing inorder. The page-level index approach only inserts a given (key, dataPageid)record once even if a key appears multiple times in the page. The record-level index approach inserts an index record for every data record. Thepage-level indexing approach has higher performance due to fewer recordsinserted into the data value index. It is also noteworthy that the index sizeis considerable relative to the data size.The insert experiment was repeated on the 32-bit platform using both theSD card and DataFlash memory for storage. Figure 4.12 displays the insertperformance on the DataFlash memory. The results are consistent with theresults on the ATmega2560 platform. The number of I/Os are identical.The faster processor speed reduces the CPU overhead of the SBITS andpartitioning methods that have relatively better performance compared tothe sequential file. The B-tree performance remains significantly slower.Note that only the B-tree page level index is shown due to very high insertcost when indexing by record as shown in the previous experiment.The absolute insert performance is slower for the DataFlash memorydue to the cost of erasing before write. If the memory chip is pre-erasedbefore inserts are performed, then the insert performance is three timeshigher. In general, the algorithm cannot be guaranteed that pages havebeen previously erased and must explicitly erase pages before writing. Unlikewriting on a SD card, the algorithm must handle page erase, wear leveling,and ensure that it is managing memory directly as there is no FTL. In thisraw memory environment, sequential algorithms like SBITS are easier andmore efficient to implement as they write data pages sequentially. The B-634.6. EXPERIMENTAL RESULTStree with its random writes consumes significantly more memory pages andmemory management is much more complicated.Figure 4.12: Index Insert Performance on 32-bit Platform using DataFlashThe performance on the 32-bit platform using the SD card was consistentwith the performance on the SD card on the ATmega2560. The absoluteperformance was about twice as fast as the ATmega2560 SD card and theDataFlash memory. Figure 4.13 presents the relative performance of eachindex method compared to using a sequential file on both platforms. Therelative performance is presented as a reduction in insert rate comparedto using a sequential file, so smaller numbers are better. On all platformsand memory types, SBITS is superior with no more than a 10% insert ratereduction. The partitioning approach varies between 15% and 30% ratereduction. The slightly higher variation is related to the partitioning ap-proach having less relative performance loss for CPU intensive operationsduring the partitioning on the 32-bit platform compared to the 8-bit AT-mega2560. The sequential B-tree insert rate is affected by its higher I/Os,and this is a larger factor on the faster 32-bit platform. The B-tree has aninsert rate of less than 10% of a sequential file due to high I/Os.4.6.2 Timestamp Query PerformanceQuerying by timestamp is very common in time series data and is of-ten used for timestamp range searches. Timestamp query performance wasmeasured by performing 10,000 random timestamp queries on the data filecontaining 100,000 records produced during the insert experiment. The re-sults are in Figure 4.14.Querying by timestamp on the sorted data file requires a binary search644.6. EXPERIMENTAL RESULTSFigure 4.13: Index Insert Performance Compared to Sequential Filewith about 11 page reads per query. The bitmap and partitioning tech-niques use the modified interpolation search algorithm of SBITS [FOL21]that predicts the next page based on the data distribution. With the oneminute data set, even though there are gaps in the data that make it notconsistently one minute intervals, the algorithm can find the record in anaverage of 2.5 page reads. Note that the sorted data file could also use thisapproach in practice, and would be the recommended approach. Binarysearch was shown for comparison.Figure 4.14: Index Timestamp Query Performance on ATmega2560Both the B-tree and sequential B-tree perform a timestamp query usingthe same sequential B-tree index. The difference in performance is exper-imental variation. The query performance is very good but slightly slowerthan the interpolation search algorithm. An advantage of the B-tree is thatthe performance is consistent for all queries and requires 3 page reads with654.6. EXPERIMENTAL RESULTSFigure 4.15: Timestamp Query Performance on 32-bit platform withDataFlash Memorythe first page read always the root that is buffered in memory.It is important to highlight that the read performance is an order ofmagnitude slower than the insert performance seen previously despite writesbeing slower than reads for the storage hardware. Every query requires atleast one page read to answer. In comparison, the inserts are buffered on aper page basis. A page is only written when full (31 records). This allows theinsert performance to be higher than the query performance. For a use casewhere every record must be written to storage immediately after sampled(record-level consistency), the insert performance is considerably lower.Figure 4.15 displays the timestamp query performance on the 32-bitplatform on the DataFlash memory. Consistent with the results on theATmega2560, the bitmap and partition approaches that use interpolationsearch are slightly faster than using the B-tree index for searching. Theabsolute query rate is higher on the faster hardware and memory, but therelative performance is similar due to the identical I/Os on both platforms.4.6.3 Data Query PerformanceQueries on the time series data values are used for aggregate calculationsand to determine outliers. For the temperature data set, it is valuable todetermine very low or high temperatures (e.g. temperature < 35). Withoutan index on the data values, the only way to answer these queries is to scanthe entire data set. As the data stored increases, a full data scan becomesincreasingly costly.The data query performance was measured using 100,000 records of the664.6. EXPERIMENTAL RESULTSone minute sample temperature data. Each temperature value in the dataset was queried, and the average of all times was calculated. Results are inFigure 4.16.Figure 4.16: Index Data Query Performance on ATmega2560A data value query on the sequential file requires reading all 3226 pagesof the data file regardless of the query value. The bitmap index queryperformance is on average over 1.2 queries/second, which is double the per-formance of partitioning (0.6 queries/second). The bitmap index is moreselective requiring fewer data page reads. The partitioning approach is lim-ited based on the number of partitions (P = 10), so with uniform data onaverage 10% of the data file is read for each temperature queried. However,the temperature data is not uniform with certain temperatures much morefrequent than others. These results are consistent with results reported inMicroHash [ZYLK+05] where more data pages are read for frequent tem-peratures.The fundamental issue with partitioning, as mentioned previously, isimproving query performance requires increasing the number of partitions.Increasing the number of partitions is bounded by the limited memory, andinsert performance dramatically degrades with too many partitions for theavailable memory. The bitmap approach allows for finer subdividing of thedata set. Using the standard 64-bit range partition bitmap, allows for 64distinct partitions and finer selectivity during queries.The B-tree performance is very high, especially for the record-index ver-sion. The record-index B-tree can answer queries on data value entirely byusing the index without reading the data file at all. The page-index B-treerequires reading the data page to get all values for a given temperature inthat page. Overall, the cost of the inserts building the index pay off when674.6. EXPERIMENTAL RESULTSperforming queries on the index after it is built.Figure 4.17: Index Data Query I/O PerformanceFigure 4.17 shows the I/O performance of the index approaches. Thesequential file is not shown as it reads all data pages. SBITS reads all indexpages (53 pages), and as many data pages as required based on the bitmaps.Compared to the partitioning approach, it reads more index pages but sig-nificantly fewer data pages. This is due to the partitioning approach onlyreading index pages for one of its partitions for each query. The partitioningis not as fine due to P = 10, which results in reading more data pages. TheB-tree versions read fewer pages, with the record-index B-tree only requiringreading index pages.The data value query experiment was repeated on the 32-bit platformfor both the SD card and DataFlash memory. The data value query per-formance relative to the sequential file query performance is in Figure 4.18.Higher values are better as the chart displays query rate improvement com-pared to the sequential file. SBITS has a query rate 10 times higher thanthe sequential file on all memory types and has the double the improvementcompared to the partition method. A B-tree index has between 20 and 30times query rate improvement. The relatively higher performance of theB-tree on DataFlash memory is partially due to the higher random readperformance on the DataFlash.4.6.4 Results DiscussionThe experimentation on two hardware platforms demonstrate the ad-vantages and tradeoffs of various techniques for indexing time series data onembedded devices. In the majority of use cases, the number of insert opera-684.6. EXPERIMENTAL RESULTSFigure 4.18: Relative Data Query Performance on All Platformstions, performed after each sample, is significantly larger than the number ofqueries. Sequential files are the simplest and highest performing data struc-ture for insert workloads. The SBITS bitmap approach requires minimalspace overhead (<2%) and has insert performance within 10% of a sequen-tial file. Range based partitioning may work well, but its performance ishighly dependent on the data set and the range of data values in a page.For slowly changing data, the performance is good, but rapidly degradesif there is not enough memory to buffer a page per partition. Given thatSBITS has higher insert performance and stability for all data sets, it isthe better choice over range partitioning. B-tree variants have low insertperformance due to the high number of random reads and writes. However,the performance, even on low-end hardware, is still sufficient to support tensof samples per second.Queries on timestamp can be answered either using binary search on thedata file, interpolation search, or using a sequential B-tree. For regularlysampled time series data, the performance of predicting the page locationbased on known sampling frequency and record sizes using interpolationis efficient to implement and significantly outperforms binary search. In-terpolation search can be used instead of binary search for sequential files,bitmap, or partition indexes. Data sets with more variability could use moresophisticated models as developed for learned indexes [FV20, MKvR+20].Using a sequential B-tree to index the time series data has consistent queryperformance with minimal overhead. Although slightly slower for large datasets, its consistent performance would be valuable in cases where sampling isinfrequent and it is difficult to accurately determine a record location usingthis data.694.6. EXPERIMENTAL RESULTSIf the use case requires any queries on the time series data value, anindex on the data value has major benefits. Even though a sequential filehas fast insert performance, executing one query requires reading all the datavalues and would significantly weaken overall system performance. SBITShas 10 times the query performance with only a 10% reduction in insertperformance. It represents the best compromise between insert and queriesfor workloads with moderate query loads. SBITS dominates the partitioningapproach for query performance. B-trees offer superior query performanceand are recommended when the number of queries is very high relative tothe number of inserts.70Chapter 5B+tree IndexingPrefaceThis chapter is adapted from the published work in [OFL21].5.1 OverviewThis chapter presents a memory-optimized B-tree implementation thathas high performance for embedded devices. The B-tree requires only twopage buffers plus less than 100 bytes of RAM for state and temporary vari-ables. The implementation uses no dynamic memory (i.e. malloc()) andperforms all its functions with the pre-allocated buffers and state variables.This allows the B-tree to use less than 1.5 KB of memory and require onlyabout 10 KB of flash code space. Using various memory saving techniques,this reduces the memory usage by about three times compared to otherimplementations.The contributions are:− A memory-efficient B-tree implementation that requires only 2 pagebuffers and less than 1.5 KB of RAM.− Optimizations to reduce the number of memory buffers used duringthe split operation for a record insert.− A performance evaluation on memory-constrained embedded devicesthat demonstrates the efficiency and practical use of the B-tree forsensor data collection and analysis.There are implementations of flash-optimized B-trees that adapt to flashcharacteristics using one of two approaches. The first approach defers writesby buffering nodes in memory instead of writing them immediately afterupdate. Write-optimized trees [BFJ+15] buffer modifications and write themout in batches to amortize the write cost and avoid small random writes.715.2. B-TREE IMPLEMENTATIONStrategies based on buffering have limited use on embedded devices as thememory available is too low to buffer enough data for a significant benefit.The second approach logs changes to the tree rather than updating thetree immediately. The logged changes may be recorded in another area inmemory/flash [RKLP14, WKC07a] or in special areas of the flash data page[KL15, NLM12]. Log-structured merge trees (LSM-trees) [OCGO96] consistof multiple levels of B-trees with the top-level buffered in memory. LSM-tree variants offer high write performance with a trade-off of lower readperformance and a large amount of memory consumed. For certain memorytypes, it may be possible to perform partial page flash updates in restrictedcases [HKVP19].Sequential indexing techniques such as MicroHash and SBITS index se-quential time series data rather than a general data set. There is no pub-lished work on a B-tree implementation for small memory embedded devices.Existing B-tree implementations for flash memory/SSDs achieve higher per-formance by exploiting I/O parallelism of SSDs and the extensive memoryavailable on servers for buffering updates. These implementations are notexecutable on the embedded platforms investigated as SRAM is extremelylimited. This chapter presents a B-tree implementation that is efficient forthe smallest embedded devices.5.2 B-tree ImplementationThe primary challenge with implementing a B-tree for embedded devicesis minimizing memory usage. The absolute minimum memory required istwo buffers: one write buffer for page modifications and one read buffer forreading pages. The implementation uses the write buffer for record insertsand tree modifications. An active path is the path from the root to a leafnode. Figure 5.1 contains pseudocode for the insert operation, and Figure5.2 describes the split operation.When performing a split, the input is the record to be inserted in the fullnode and a left and right child pointer if the node being split is an interiornode. There are two cases. If the insertion location of the insert record intothe node is less than the mid point (where the split is being performed),then it is necessary to shift records down from the insert location to makeroom for the record to be inserted. The record is inserted, and the left pagewith the smaller values in the split is written to storage. Note that the pageis not cleared of the records that are no longer in this page, only the countof the number of records is updated. This old record data at the end of the725.2. B-TREE IMPLEMENTATIONfor each level of the tree starting at the root:read page into read bufferstore page id in active pathsearch page to find next child node to readread leaf node into write bufferif space available on page:insert record in sorted order on pagewrite page to storageelse:perform splitFigure 5.1: B-tree Insert Implementationpage is ignored. Not overwriting these records is necessary to avoid needinga second buffer. To create the right page with the larger values, the midpoint record is copied to the start of the record followed by the remainingrecords on the page.The case where the insertion location is after the midpoint is similar.Updating the left page requires only updating the count and writing out thepage. The right page is produced by shifting the records to the front of theexisting page and inserting the new insert record in the proper sorted order.After one iteration is completed, there is a new insertion record contain-ing the mid point record in the split with its associated left and right childpointers. Splitting may occur all the way to the root in which case a newroot node is built with the record and left and right pointers. The pathfrom root to leaf during the insert is stored in an array when searching forthe insertion leaf so that it is easy to backup the path when handling splitsstarting at a leaf.5.2.1 Example and AnalysisFigures 5.3 and 5.4 illustrate the insertion and splitting process. Bothinterior and leaf nodes have a maximum of 4 keys. The value inserted is165. During searching for the insert leaf, the algorithm tracks the insertpath from root to leaf, which in this example are nodes with ids A1, A2,andA3. The leaf node is full so a split occurs of the leaf. The insert locationis at index 1. The first step buffers the mid record 175 at index 2. Record170 is shifted down a location and record 165 is inserted at index 1. Theleft page is written to storage. The mid record 175 is then copied to the735.2. B-TREE IMPLEMENTATIONwhile not above rootif space available on page:insert record in sorted order on pagewrite page to storagereturnmid = count / 2insertLoc = insertion location in node for keybuffer record at mid in temporary record storageif insertLoc < mid:// Configure small (left) page in the splitshift records starting at insertLoc down 1write insert record to location insertLocupdate record countwrite (left) page to storage// Configure large (right) page in the splitwrite record in temp storage to start of pagecopy records after mid to start of pagewrite (right) page to storageelse:// Configure small (left) page in the splitset count of page to mid+1write (left) page to storage// Configure large (right) page in the splitcopy records after mid and before insertLocto the start of the pagewrite insert record at insertLoc -midcopy records after insertLoc to start of pagewrite (right) page to storagecurrent node is next node on active pathcreate new rootadd record to rootadd left and right pointers to rootFigure 5.2: B-tree Split Implementation745.2. B-TREE IMPLEMENTATIONstart of the page and the remaining records in the block copied after it. Theright page is written to storage. The insertion at the next level up (A2) is175 with the left and right pointers to the pages just written. This blockalso overflows. The mid record is 160. The left page contains only 120 and130 and requires no record copying. The right page begins with the insertedrecord 175 and the remaining records in the block. There is space in the root(A1) which is updated with the new key (160) and left and right pointers.Figure 5.3: B-tree Before Insert of 165Figure 5.4: B-tree After Insert of 165Given a B-tree of height H, the insert operation requires H reads whensearching for the leaf node, and a maximum of 2 ∗ H + 1 writes if thesplit operation splits nodes all the way to the root. For most use cases, theheight is less than 5 and splits are infrequent. Only 1 write buffer is requiredregardless how many splits are performed. This is a significant improvementcompared to previous implementations that would use two buffers for eachsplit level (i.e. up to 2 ∗ H buffers). Thus, the insert performance is veryefficient. Given that only one buffer is used for writes, the B-tree can usethe other buffer(s) to concurrently perform queries without affecting theupdates.Searching for a key requires H reads. Multiple readers can use the B-treestructure concurrently. Deletion is rare for embedded use cases, and nodesthat are under full are not merged. This reduces the writes performed.755.3. EXPERIMENTAL EVALUATION5.3 Experimental EvaluationExperiments test the B-tree implementation performance on an ArduinoMEGA 2560 that uses a 8-bit AVR ATmega2560 microcontroller and has256 KB of flash program memory, 8 KB of SRAM, 4 KB EEPROM, andsupports clock speeds up to 16 MHz. Storage was on a 8 GB microSD cardattached with an Arduino Ethernet shield. The page size was 512 bytes.There were no hardware buffers on the SD card accessible to the algorithm,so all page buffering was in RAM. With a page size of 512 bytes, the practicallimit of the number of memory buffers, M , on the device was M = 8 (4 KB)as the rest of the RAM was used for other functions. The memory usage forthe B-tree was 1.5 KB (for M = 2) and the code space usage was 10 KB(about 1500 lines of code).The SD card sequential read performance was 345 pages/second (172KB/second), and sequential write performance was 175 pages/second (88KB/second). Random read performance was also 345 pages/second (172KB/second). The write-to-read ratio is 1.95. On this hardware, data trans-mission on the bus limited performance as much as the raw SD card perfor-mance characteristics.The experimental data set was chosen to be representative of real-worldsensor data sets that often consist of an integer key or timestamp and somecollected data. The data records were 16 bytes with a 4 byte integer key.With a page size of 512 bytes, the number of records per page was 31 aseach page had a page header that consumed some space. The page headerstores the page id and the count of the number of records in the page.The number of interior records per page was 62. Each interior record is 8bytes consisting of a 4 byte integer key and a 4 byte page id. Data setswere randomly generated. The results are the average of three runs. Giventhat there are no previous B-tree implementations that run on the memory-constrained hardware, the experiments are designed to demonstrate how theB-tree implementation can be used efficiently for practical, real-world datacollection use cases.5.3.1 Insert and Query PerformanceFigure 5.5 shows the time to insert up to 10,000 records (160 KB) forM = 2. At 10,000 records the data size is 80 times larger than the RAMavailable. In server systems with more memory available, this ratio is be-tween 2 to 10. The height of the tree is 3 by 10,000 records, and the overalltime is linear in the number of records inserted.765.3. EXPERIMENTAL EVALUATIONFigure 5.5: B-tree Insert TimeFigure 5.6 shows the number of read and write I/Os for the insert. Theperformance is extremely consistent and exactly follows the expected the-oretical performance formula. Each insert requires H page reads with Hbeing 3 starting at 3000 records. Every insert requires at least 1 write. In-serting 10,000 records requires 10,940 writes which is only 9.4% more writesthan the minimum of 10,000 writes required if every record is written tostorage immediately.Figure 5.7 shows the time to query 10,000 random records (160 KB) forM = 2 from a B-tree with 10,000 records. Figure 5.8 shows the number ofreads. Each record query requires H = 3 page reads, and the performanceis linear and stable. In comparison to sequential files which are often used,retrieving a record in a sequential file requires log2(N) reads where N is thenumber of data pages. For this experiment, this results in 161 page readswhich is over 50 times larger.The results show that the implementation performs inserts and queriesefficiently with a minimal amount of memory.5.3.2 Memory BufferingThe implementation is designed to use additional memory provided be-yond the minimum two buffers. If given an additional buffer, the buffer isused to buffer the root node as this results in the greatest performance ben-efit. Any additional buffers beyond three are allocated using a least-recently775.3. EXPERIMENTAL EVALUATIONFigure 5.6: B-tree Insert I/OFigure 5.7: B-tree Query Time785.3. EXPERIMENTAL EVALUATIONFigure 5.8: B-tree Query I/Oused (LRU) algorithm. With random inserts and queries, besides the root,the pages requested are random and the buffer hit rate is low.Figure 5.9 shows the time to insert 10,000 records and query the 10,000records in random order for various values of M . Figure 5.10 shows thereduction in reads during insert and query asM increases. The experimentsshow that additional memory has advantages, but the jump to M = 3is the biggest benefit. Adding a third buffer increases the buffer hit rateto 33% for queries and almost 40% for inserts, which makes sense giventhat the root is used in every query and insert operation. The third bufferdecreases the insert time by 20% and the query time by 30%. Additionalbuffers slightly decrease reads, but the buffer hit rate improvement is lowas the pages accessed are random. Thus, designers with limited memoryare typically deciding between M = 2 or M = 3 and additional memoryis less useful. For real data with high duplication and clustering, such astemperature data, the buffer hit rate during insert is already quite high anddoes not significantly improve with the addition of more buffers. However,read performance does improve with increased buffer hits resulting fromadditional buffers.5.3.3 Example Use CaseThe previous experiment results demonstrate the efficient performanceof the B-tree implementation. In practice, it is important that the B-tree795.3. EXPERIMENTAL EVALUATIONFigure 5.9: B-tree Time Performance with Increasing MemoryFigure 5.10: B-tree I/O Performance with Increasing Memory805.3. EXPERIMENTAL EVALUATIONis deployable in real-world sensor data collection environments. An exam-ple use case is collecting environmental data for sustainable agriculture andenvironmental analysis. In [FL10], soil moisture data was collected to de-termine optimal irrigation patterns to reduce water usage. The data wassampled every minute, stored on the device, and used to control the irriga-tion system. The system was effective but required custom implementationof data structures for data storage.A key metric is the time to perform a single insert as this limits thefrequency that the sensor can sample data. The B-tree implementationwith M = 2 requires 20 ms per insert and 8 ms per query. For M = 3, thetime is 15 ms per insert and 5.5 ms per query. Given this performance, adeployment using the B-tree can sample up to 50 times/second. In practice,most use cases sample every minute or 15 minutes, and the percent timespent on data storage is less than 0.03%.Overall, the B-tree implementation provides an efficient data structurefor data storage on embedded devices and supports practical use cases ofdata collection with minimal memory and power usage. The code is availableon GitHub (https://github.com/ubco-db/btree) with an open source li-cense to allow it to be used by the community.81Chapter 6VMtreeThe B-tree [BM72] is a widely-used, high-performance index structurefor database applications. Most implementations use the B+-tree variant[Com79] where data records are only in the leaf nodes, and interior nodescontain keys for navigation. An example B+-tree is in Figure 6.1, whereeach node contains a maximum of 3 entries.Figure 6.1: B+-tree ExampleThere is a long history of B-tree implementations with initial focus onhard drives. Graefe [Gra12] provides a detailed discussion of numerous chal-lenges, techniques, and best practices for B-tree implementation. Foster B-trees [GKK12] combine the advantages of several B-tree variants includingthe write-optimized B-tree [Gra04] to support improved concurrency andefficient page migration in flash storage. Foster B-trees eliminate siblingpointers in the B-tree structure (dashed pointers in the figure) and rely onlyon parent-children pointers.Virtual memory and shadow paging techniques [RHB+90] have been ap-plied to B-trees. Gray [GR93] describes how database page virtual addressesare used with a mapping table for converting virtual to physical addressesand avoiding updating the complete path from leaf to root. A mappingtable was also used in Bw-trees ([LLS13, WPL+18]) for high-concurrencyB-trees in main memory databases and supporting log-structured storageon servers. The implementation performance of the mapping table is criti-cal. B-tree algorithms [Rod08] were developed that are efficient for cloningand shadowing with good concurrency for use with file systems. When up-82dating a page using shadowing, the page is written back to disk at a differentlocation and ancestor nodes must either be shadowed to the root or a vir-tual mapping created. Prior work on shadowing and virtual addresses wasprimarily focused on improving the concurrency of transactions, but it ispossible to adapt it for use with raw flash memory on embedded devices.Batch updates [PMSSY96] to B-trees are also relevant including supportfor concurrency. Increased performance is possible by sorting keys and ap-plying inserts in batch. This work supports a single writer given the simplerhardware and use case.The migration from hard drives to flash-based storage and solid-statedrives (SSDs) resulted in a renewed emphasis on B-trees and optimizationfor the flash characteristics [FABM20]. The key benefit of flash is the signif-icantly higher random access performance compared to the high seek timesfor hard drives. This motivates having B-tree nodes of smaller size whenstoring on SSDs compared to hard drives. A challenge is handling the flashmemory property that in most cases a physical page cannot be overwrittenin-place without first performing a block erase. Writes are often more costlythan reads leading to asymetric performance.B-tree implementations adapted to flash memory properties by favoringreads over writes, using in-memory buffers and logging to reduce the numberof writes, and deferring and batching random writes into sequential writeswhen possible. An SSD has an internal CPU and memory and is capable ofprocessing multiple requests simultaneously. As SSD technology has evolved,the performance difference for reading and writing has been reduced by theinternal hardware in the SSD that uses its flash translation layer (FTL)algorithm to intelligently allocate physical memory pages and manage themappropriately. The internal operation of an SSD is a black-box, but B-treeimplementations that exploit parallelism have advantages.To understand a fundamental challenge, consider inserting key 50 intothe B-tree in Figure 6.1. Key 50 will be inserted into the second leaf nodecurrently containing 40 and 60. On a hard drive, the page containing thenode is updated and written back in-place on disk. No modifications to theB-tree structure are required. On an SSD, the B-tree implementation mayalso overwrite the page logically, but the SSD must use its FTL to write thepage to a different physical location as overwriting the same location withouterasing is not supported. A sequence of multiple writes to different pagesappears as random writes to the SSD, which generally are not processed asefficiently as writing sequentially.For raw flash memory chips that do not have an FTL and file interface,the B-tree implementation must change. It is not possible to physically83overwrite an updated page, and writing to a new page location requiresupdating B-tree pointers. Updating a pointer may require cascading updatesto other pages. In our example, inserting 50 and writing the updated page toa new location requires updating the pointer in the parent node containing(40,70) that then triggers an update and write of the root node. Further,if sibling pointers are used, the leaf node containing (10,20,30) would alsorequire updating. Reducing this write amplification is critical to ensureacceptable performance.A survey on flash based indexing [FABM20] overviews various B-tree im-plementations. Buffering approaches such as write-optimized trees [BFJ+15]defer writes by buffering nodes in memory and writing in batches to amor-tize the write cost and avoid small random writes. Logging approaches[KL15, NLM12, RKLP14, WKC07a] log changes in memory or on the flashdata page rather than updating immediately. In our insert key 50 example,a buffering approach may buffer the leaf node and its parent in memory andonly write the nodes after many updates have occurred. A logging approachwould store the insert 50 as a log record in a separate memory area and defermaking changes to the tree itself. The tree is updated in batch when the logarea is full. Using memory for buffering or logging allows implementationsto improve performance by maximizing parallel usage of SSD hardware re-sources and capabilities. Benchmarking tree performance on SSDs [DISK20]is affected by SSD architecture and performance. Although less of an issuefor SD cards and raw memory, the properties of the SD card storage do havean impact.Raw flash B-tree implementations often modify the B-tree node struc-ture to reduce the write amplification. It is necessary to manage memoryin these implementations including free space and garbage collection. Someimplementations exploit flash memory properties such as partial page up-dates or overwrites [KMB13, HKVP19]. Using a mapping table such as doneby Bw-trees ([LLS13, WPL+18]) may reduce or eliminate write amplifica-tion as any physical page movements are captured by updating the mappingtable rather than the pages containing the logical ids or pointers.B-tree implementations designed for flash memory and SSDs are notexecutable on memory-constrained devices unless they are adapted to thelow memory available. Techniques based on buffering and deferred writeshave issues due to the limited memory available for buffering. A B-treeimplementation [GKK12] for embedded devices that uses limited memory isavailable but is not optimized for raw flash and relies on file-based storage.Other index structures for memory-constrained embedded devices in-clude Antelope [TD11b], MicroHash [ZYLK+05], PBFilter [YP12b], and846.1. MOTIVATING ENVIRONMENTSBITS [FOL21]. These index structures, typically for sequential time se-ries data, use sequential writes and minimize memory usage. They do notsupport indexing for non-sequential data like a B-tree.6.1 Motivating EnvironmentThe target environment is resource-constrained embedded devices pri-marily used in logging and monitoring applications. The device may have aCPU speed of 16 MHz to 128 MHz, between 4 KB and 64 KB RAM, anduse NOR, NAND, or SD card storage. The flash storage may not have anFTL or file system. The flash storage size depends on the data collectionrequirements and may be between 8 MB to 1 GB. These hardware specifica-tions (see Figure 6.2) are comparable to the IBM 360 machine used in 1970for the original B-tree experiments.Device CPU RAM I/O RateM0+ SAMD21 48 MHz 32 KB 450 KB/sPIC24FJ1024 16 MHz 32 KB 200 KB/sIBM 360/44 [BM72] 1.6 MHz 32-256 KB 156 KB/sFigure 6.2: Example Embedded Devices compared with Original Experi-mental B-tree Hardware in 1970A page is the I/O unit for flash storage and has size between 256 and4096 bytes. A page must be erased before it is written. Erasing is donein units of blocks, which are consecutive pages. Writes are not performedin-place due to the cost of erasing a block. If SD card storage is used, theflash translation layer (FTL) writes to a new physical location and updatesits internal logical to physical page mapping. When using raw memorywith no FTL, the algorithm must manage physical page allocation, garbagecollection, and wear leveling. Some NOR flash memory supports limitedpage overwriting [Ade24]. It is possible to overwrite a page as long as nobits are changed from 0 to 1. Bit changes from 1 to 0 are acceptable. Thisis achievable by initializing a page to all ones and appending to free spacein the page that has not been previously written.The logging environment domain is characterized by very constrainedand specific data access requirements. The devices are typically collectingtime series data consisting of a timestamp and a sensed value which is oftena small number. The schema is simple, and the queries performed are known856.1. MOTIVATING ENVIRONMENTat design time.Highly efficient inserts are the key consideration. Record inserts aretypically append-only in order of record timestamp. Updates and deletes arevery rare. Bulk deletes may occur periodically when the device eliminateshistorical data. For example, older data may be deleted from the system ona daily basis after it is no longer useful or has been transmitted to a serverfor processing. Query processing on-device is for performing searches bytimestamp or value and aggregate queries over time windows. These queriesare generated by the device as part of its functions and are generally knownbefore deployment.The very low RAM challenges data processing, and minimizing memoryusage is critical. The RAM to storage ratio is lower than server basedsystems [AGBA19]. For example, if 4 KB RAM is available, that is 1% of a400 KB data size and 0.1% of 4 MB data size.Failures are more common in embedded devices, so data structures thatare resilient to failures and do not rely on external logging support areadvantageous. There are three levels of consistency:− Record-level consistency - every record captured by device must bewritten to storage immediately− Page-level consistency - a page of records can be buffered in memorybefore having to be written to storage− Time period consistency - records can be buffered in memory for agiven time before having to be written to storageThe device may need to manage its own flash storage without a filesystem. There are three storage configurations considered:− File system with FTL support− Raw memory with no FTL− Raw memory with no FTL with page overwriting supportedThe B-tree implementation should adapt to these different device prop-erties. There are two distinct use cases for embedded indexing. Indexing theappend-only, sorted time series data is important for fast retrieval based ontimestamp. Numerous prior index structures that utilize sequential writes,including simple sorted files, demonstrate good performance with minimalmemory usage [FOL21, FABM20, TD11b, YP12b, ZYLK+05]. Even when866.2. B-TREE OPTIMIZATIONSoptimized for sequential, ordered data, the B-tree has comparable, but notsuperior, performance to these specialized index structures [OKFL22].Indexing the data values efficiently is a better opportunity for B-trees.Retrieval by data value in the time series is not as efficiently handled bycurrent embedded index structures. There is no ordering of the data values,and the index must handle random writes to any location. There may also bea considerable amount of duplication in the data set. Further, if the sensoris capturing physical measurements of the environment, the data may bemore periodic and follow a function based on the value being measured.As an example, temperature values change slowly over time in a relativelypredictable fashion. The focus of this work is on indexing non-sorted dataefficiently.6.2 B-tree OptimizationsThis section presents B-tree optimization and implementation variantsfor the embedded environment. Previous work based on logging and writeoptimized trees [BFJ+15, KL15, NLM12, RKLP14, WKC07a] are combinedand compared with an approach that uses virtual mappings [LLS13, WPL+18]to defer writing nodes when their children pointers change. Although previ-ous B-tree implementations may not be directly executable in this environ-ment as they either consume too much memory or rely on operating systemfeatures that are not available, the key optimizations are transferable andadaptable.6.2.1 Buffering and LoggingMany B-tree approaches optimized for flash memory rely on either buffer-ing updates to defer writes or logging changes to later perform the operationsin batch. Adapting these techniques to the embedded environment requireshandling that the memory available is very small. There is often only suffi-cient memory to buffer the root node and a few nodes in the working path,and not enough to buffer even a small fraction of the children nodes of theroot.Given these constraints, an approach that updates a B-tree node directlyin the buffer and defers writing to storage has minimal performance benefitas a page will not remain in the buffer for long to accumulate multipleupdates before being written to storage.Logging operations to perform in batch is more memory efficient as onlythe operation must be buffered rather than the page that was modified.876.2. B-TREE OPTIMIZATIONSThis allows for more modifications in the limited memory. The diversityof previous log-based approaches associated logs with either the entire tree,individual nodes, or based on storage blocks. The most memory efficient isto use a single log for the entire tree. When the log is full, the operationsare sorted, and the inserts are performed in batch. This may reduce I/Os byinserting multiple records into a page at one time, and may have especiallygood performance for data that has clustering of similar values.The logging optimization performing batch inserts can be applied inconjunction with any of the other B-tree optimizations. Given a fixed logbuffer size, batch updates are performed when the log buffer is full. Forapplications that have restrictions on data loss, the log buffer can be sizedto require log operations to be performed after a given amount of time orrecords have been accumulated.6.2.2 Virtual MappingsStorage devices such as SSDs and SD cards support logical page over-writing as the FTL translates logical writes of pages in a file to physicalmemory locations on the device. At the hardware level, the storage devicemust translate logical page requests to physical locations and maintain in-formation on pages that are no longer valid. Transparent to the application,the device erases blocks containing invalid pages and maintains its storageallocations.Since it is not possible to update in-place on raw flash storage, updatinga node results in writing to a new physical page, and B-tree pointers tothe previous physical page must be updated. Updating pointers cascades tomany nodes in the tree, and writing a leaf node may result in writing theentire leaf-to-root.Virtual mappings are a technique to handle the write amplification issuewhen writing B-tree nodes on flash storage that does not have an FTL. Sinceit is not possible to implement an FTL in the limited device memory, virtualmappings are a B-tree specific translation mechanism. A virtual mapping isa pair consisting of its previous and new page id (prevPageId, newPageId).Whenever a page is written to a new location, a virtual mapping is insertedinto the mapping table.Virtual mappings are similar to the mapping table used in Bw-trees[LLS13, WPL+18] with some important differences to make the implemen-tation feasible on embedded devices. The mapping table used in Bw-treeswas an array indexed by logical page id, which are 64-bit integers. Thephysical page address was stored in the array location. For example, the886.2. B-TREE OPTIMIZATIONSphysical page address of logical page ID 1 would be in array location 1.Changing the physical page address is done simply by updating the value inarray location 1.An embedded device does not have sufficient RAM to store an arrayof all possible logical id to physical page mappings. Our virtual mappingtable stores physical page id mappings from a previous page location to anew page location. All pointer addresses are physical addresses (not logicaladdresses as used in Bw-trees). When a page is moved from physical locationP to new physical page location P ′, a mapping is inserted into the mappingtable (P, P ′). Thus, there are only mappings in the table when a page hasmoved physical locations. This greatly reduces the size of the mapping tablecompared to what is used in Bw-trees.A physical page id is mapped to a physical address based on the startingmemory address and multiplying the id by the page size to use as an offset.The virtual mapping table is maintained in memory. Whenever a pageretrieval is to be performed, the virtual mapping table is consulted to seeif the address has changed. The B-tree implementation controls the virtualmapping table and its management in the limited memory.Virtual mappings resolve the write amplification issue. In the examplewhen inserting key 50, the node containing (40, 60) is updated and writtento a new location. The parent node containing (40, 70) requires a pointerupdate to point to the new location. Rather than modifying the parentnode, a virtual mapping is created. Whenever the pointer is traversed, themapping table is used to lookup if a new location is used.To minimize the number of mappings, similar to Foster B-trees [GKK12],there are no sibling pointers. This enables easier migration of pages on stor-age. This technique expands on Foster B-trees by explicitly managing flashstorage and using virtual mappings to transparently allow page movementwithout disrupting the B-tree structure. Virtual mappings allow parentpages to have their updates deferred. A virtual mapping record has size of4 or 8 bytes depending on the number of pages in storage. In general, thevirtual mapping table may grow much larger than the available memory.Given a bounded amount of memory for the mapping table, mappingscan be removed from the table either during an insert operation or in be-tween B-tree operations. During an insert operation, the number of map-pings on each node on the path to the leaf can be determined, and the nodewritten to storage if the mappings exceed a certain amount. There is onlya net benefit in the number of mappings if a node is written that has 2 ormore mappings. This is because whenever a node is updated its mappingscan be removed (as its pointers are updated), but its parent will need a new896.3. IMPLEMENTATIONmapping for its new location. At any time, a traversal from the root can beperformed to identify nodes with mappings that can be removed. Writing afull path from leaf-to-root removes all mappings along that path.Using virtual mappings allows sequentially writing pages to storage.When a page is updated, it is written to the next sequential page location,and a virtual mapping is created. This has performance benefits for somedevices, and also simplifies free space management and garbage collection.6.2.3 Page OverwritingFor raw memory storage, the application maintains the physical memoryincluding free space management and block erases. Typically, a page thathas been previously written cannot be overwritten in-place. However, thereare some memory devices that allow limited page overwrites which can beexploited to improve performance [Ade24]. Specifically, some NAND flashallow partial page writes and NOR and Dataflash products support over-writing of a complete page given constraints. Due to the nature of NORflash, the entire page can be overwritten but only bit changes from 1 to 0are supported [Ade24, FPL16]. Practically, this allows writing to parts ofthe page that were not written to before.Overwriting may improve write performance and reduce memory wearby reducing the number of erases performed. In [HKVP19], the B-tree nodeis modified to store byte-level differences. Our implementation stores theB-tree node in linear insertion order (i.e. not sorted) which works well withoverwriting. The tradeoff is that the keys are no longer sorted in the nodeso searching requires a linear search rather than a binary search.6.3 ImplementationThis section provides specific implementation details.6.3.1 Virtual MappingsVirtual mappings must be memory-resident. Otherwise, any pointerlookup requires an I/O to determine if a mapping exists. This is a highoverhead given that most pointers will not have a mapping, but mappingsmust be checked for every pointer traversal.If a page has been changed that requires a mapping update, the mappingis added to the mapping table. If there is no space available, then the parent906.3. IMPLEMENTATIONcontaining the pointer that needs to be updated must be written. This mayhappen recursively to the root.The size of the mapping table is configurable but is typically small dueto the low amount of memory. The implementation uses an in-memory hashtable with double hashing to handle collisions. It is configurable how manyprobes are performed in the hash table before determining that a mapping isnot present. A hash table is required rather than an array used by Bw-treesas it is not possible to allocate an array in memory that stores mappings toall possible physical locations.For example, consider a raw flash storage that has a size of 4000 pageswith each page of 512 bytes resulting in a storage size of 2 MB. Represent-ing the mapping table as an array would occupy 4000 pages * 8 bytes perpage mapping = 32000 bytes = 31.25 KB, which far exceeds the memoryavailable on these devices. Using a hash table rather than an array allowsthe developer to decide how much memory they can allocate to the map-ping function, which trades off memory usage versus B-tree insert/searchperformance. A mapping table capable of storing all potential mappingswould never have any additional write amplification when a page is writtenbecause the necessary mapping could always be stored in memory.6.3.2 Free Space ManagementFree space management and garbage collection is implemented for stor-age that does not provide these functionalities. The storage is treated as acircular array. Several blocks are erased preceding the current write locationat all times. Before erasing a block, valid pages are determined and bufferedin memory or storage. Once a block is erased, the valid pages are writtenback to their original locations in the block so no mappings must be updatedin the tree.To determine if a page is valid there are two approaches. The firstapproach associates a free space bit with each page. Once a page is nolonger used, set the bit indicating it can be recycled. If there is insufficientmemory for a bit vector, a page search strategy can be used to determineif the page is valid. The algorithm to determine that any given page onstorage is a valid page is to read the page P from storage, select a key Kfrom the page, and then search the current tree for K. If K is not found ora different page encountered, then P is not a valid page and can be deleted.916.3. IMPLEMENTATION6.3.3 Page OverwritingDataflash and NOR memory allows for page overwriting. B-tree nodesthat support page overwriting are not sorted by key. Each record is ap-pended to the page. There are two bits associated with each record: a countbit and a valid bit. Both bit vectors are initialized to 1s. When a record isinserted into the page, the count bit is set to 0 from 1. The valid bit remainsas 1. If a record is moved or deleted, its valid bit is set to 0. The number ofvalid records in a page is determined by adding up all records with count bitof 0 and valid bit of 1. This structure allows for all updates to have writesof 1 to 0 as supported by the memory.Searching a page requires performing linear search. When a page is splitduring an insert, the records are sorted before dividing into the two pages.6.3.4 RecoveryEvery page header stores a page id and a previous page id. The previouspage id is -1 for a new page written for the first time. When writing a newversion of an existing page with (pageId, prevId), the previous page id forthe new page is prevId if there exists a mapping prevId → pageId else it ispageId. This allows tracking the provenance of a page and recovering thevirtual mapping table if there is a device failure or restart.On restart, the storage is scanned backwards from the last page write.During this scan, the most recent root node is identified by the page thathas the root flag set in the header and has the largest page id. When a pageis read with header (pageId, prevId), search the mapping table for prevId. Ifno mapping is found, a mapping is added to the mapping table of the formprevId → pageId. If a mapping prevId → pageId2 is found and pageId2 >pageId, then the pageId page is an older version and is marked as a free pagein the free space bitmap.Consider a leaf node at location 5 written three times due to insertingthree keys. The first page has a header with (pageId, prevId) of (5,−1).The second page has header (6, 5). The third page has header (7, 5) and thefourth page has header (8, 5). Scanning the storage backwards from the lastpage results in adding the mapping of 5→ 8 and pages 5, 6, and 7 markedas free space.If there is a failure during an insert operation, recovery to a consistentstate is possible as the previous page data is still in storage. If the failureoccurs after the leaf node is written to storage and no changes are requiredon the interior nodes above, then recovering the virtual mapping table is926.3. IMPLEMENTATIONsufficient to be in a consistent state. If the leaf node has been updated onstorage, but any splits to interior nodes were not present on storage, recoverby re-executing the insert of the key. The key that was inserted is identifiedby comparing with the previous node version.6.3.5 Implementation VariantsThe B-tree optimizations are deployed as several implementation vari-ants. The base B-tree implementation performs update-in-place writing.This implementation is only executable for storage devices that support afile system interface (with an underlying FTL) or raw flash memory thatsupports page-level erase-then-write (such as Dataflash [Ade24]). The vir-tual mapping tree, VMtree, uses a virtual mapping table to minimize writeamplification and performs sequential writes to storage. When a logicalpage is overwritten, the updated page is written to the next sequential pagelocation, and a mapping inserted in the mapping table to prevent modifyingthe parent page. The VMtree-OW implementation performs physical pageoverwrites on memory storage that supports the functionality. A virtualmapping table is not required.All implementations use a common page buffer allowing buffering com-monly used pages using a LRU algorithm. The root page is always buffered.Each implementation may also utilize a log buffer allowing batching of op-erations.Figure 6.3 shows how the different variants handle inserting key 50 intothe tree in Figure 6.1. The B-tree does not manage free space or memorystorage as its relies on the storage device for that. The B-tree performsin-place writing of logical pages, and the actual physical location can beanywhere on storage as determined by the FTL. The diagram shows addingkey 50 to the existing logical page. The B-tree has no control over thephysical page location.VMtree-OW performs overwriting on physical pages. Key 50 is insertedinto the existing physical page in the next location available. The count bitfor the location is set to 0 indicating a valid record is present at that locationand valid bit remains at 1. This overwrite guarantees all bit changes on thepage are from 1 to 0.VMtree behaves differently as it manages its free space and physicalstorage. The before and after is showing physical memory storage. Since theVMtree writes sequentially and does not overwrite any pages, it will advancethrough the storage address space faster than the other two algorithms. Thefree space bitmap is used to determine if a page is used (0) or available (1).936.3. IMPLEMENTATIONAdding the key 50 results in a new page containing (40, 50, 60) being storedat the current write point in storage at physical page address 34. The bitvector for the previous page at address 30 is set to 1 indicating the pagecan be re-used. A mapping 30 → 34 is added to the mapping table so theparent node at address 32 does not need to be updated.(a) B-tree(b) VMtree-OW(c) VMtreeFigure 6.3: Inserting Key 5094Chapter 7VMtree ResultsThe B-tree implementations and optimizations were compared on sev-eral hardware platforms for a variety of data sets. The hardware platformsand storage devices are in Table 7.1 and Table 7.2. The data set character-istics are in Table 7.3. Results are the average of 3 runs as there is limitedvariability in execution times between runs.Device CPU RAM32-bit ARM M0+ SAMD21 48 MHz 32 KB32-bit ARM M0+ SAMD21 48 MHz 32 KB16-bit PIC24FJ1024GB610 16 MHz 32 KB16-bit PIC24FJ1024GB610 16 MHz 32 KBFigure 7.1: Embedded Devices Hardware ConfigurationsDevice Storage Page Size R (KB/s) W (KB/s) R/W RatioARM SD card 512 bytes 500 ; 400 500 ; 215 1 ; 1.9ARM Dataflash 512 bytes 475 35 13.5PIC NAND 2048 bytes 203 187 1.1PIC SD card 2048 bytes 198 ; 194 108 ; 93 1.8 ; 2Figure 7.2: Embedded Devices Storage PerformanceEach hardware platform has its read and write performance character-ized. If there is more than one value, the first value is sequential performanceand the second value is random performance. SD cards generally have slowerrandom versus sequential performance that varies between cards. The rawNAND and Dataflash chips have the same performance for sequential andrandom I/Os. The Dataflash chip is unique as it allows a page level writewith an erase without requiring erasing a whole block of pages. However,this operation is much more expensive than writing over an already erasedpage. The write bandwidth of 35 KB/sec. is for the erase-then-write opera-tion, which is required for the B-tree implementation that performs in-place957.1. RANDOM DATAData Set Key Size Record Size DescriptionRandom 4 bytes 16 bytes Random, unique 32-bit in-tegersEnvironmental 8 bytes 8 bytes Time series data from[ZYLK+05]. Indexing datavalue (temperature, pres-sure, or wind speed).Health 8 bytes 8 bytes WESAD time series data[SRD+18] monitoring pa-tient heart, temperature,movement.Figure 7.3: Experimental Data Setswrites. Storage is pre-erased before an experiment begins.The buffer memory allocated to the implementations was M=3 pagebuffers. The VMtree algorithm also requires additional memory to storethe mapping table. The 32-bit SAMD21 platform used storage page sizesof 512 bytes, while the 16-bit PIC on Explorer 16/32 development boardhad page sizes of 2048 bytes. On the SAMD-21 platform, total memoryconsumed was 3141 bytes consisting of 3 x 512 byte pages, state variablesof 330 bytes, bit vector of 251 bytes, and a mapping table of 1024 bytes.On the PIC platform, total memory consumed was 8866 bytes consisting of3 x 2048 byte buffer pages, state variables of 547 bytes, bit vector of 127bytes, and a mapping table of 2048 bytes. The B-tree and VMtree-OWdid not require the memory for the mapping table or free space bit vector.Additional memory is optionally consumed when using the log buffer.7.1 Random DataThe random data set consisted of 10,000 records of 16 bytes with a 4byte random integer key. The experiment inserted 10,000 records and thenperformed 10,000 queries. The results on the 32-bit ARM processor for theSD card and Dataflash are in Figures 7.4 and 7.5.On the SD card, the VMtree I/O performance is within 3% of the B-treeimplementation. There is no advantage to maintaining a virtual mappingtable as the SD card has its own FTL and file system support. The VMtreeperforms sequential I/O versus random I/O by the B-tree, however, this967.1. RANDOM DATAbenefit was not noticeable in the results with the SD card random I/O onlyabout two times slower. It may be more of a factor for storage with muchmore significant differences. Similarly, VMtree-OW is slower on the SDcard which does not support hardware-level overwrites, as its unsorted leafstructure requires more space and time to process.On the Dataflash, the comparison between VMtree and B-tree is sim-ilar except VMtree is slightly faster as it is able to be more efficient withits erasing due to its sequential I/Os. This memory supports hardware-level overwrites, which results in a dramatic performance improvement forVMtree-OW with its overwrite-friendly page structure.Figure 7.4: Insert Performance on SD Card Compared to B-Tree (ARM)Figure 7.5: Insert Performance on Dataflash Compared to B-Tree (ARM)The introduction of a log buffer improves all implementations. Log bufferresults of size 1, 2, and 4 pages are in Figures 7.6 and 7.7 for the SD card andDataflash respectively. These figures perform a comparison for each B-treevariant without a log buffer compared to the addition of a log buffer. Thebenefits of the log buffer are the same as for batch index insertion [PMSSY96]977.1. RANDOM DATAwith signification reduction in read and write I/O and overall time. Thereis no difference in I/Os between the different B-tree implementations on thetwo storage types. The time varies slightly based on the read and writeperformance of the storage.Given memory space, a larger log buffer increases the opportunities tobatch writes to the same leaf node resulting in more I/O and time reduction.There is a slightly higher benefit for a log buffer for the VMtree as batchingoperations also reduces the number of virtual mappings used and virtualmapping lookups during tree traversal. A log buffer of size 1 (512 bytes)reduces insert time by at least 20%. Figure 7.8 shows the insert throughputfor each B-tree variant at various log buffer sizes.For queries, the number of read I/Os is identical for all implementations.The query time is within 2% for VMtree and B-tree. VMtree-OW is 10 to20% slower due to its unsorted nodes requiring linear search.The results on the smaller 16-bit PIC device are similar. Figure 7.9displays the relative random insert performance on a SD card and NANDfor the B-tree and VMtree. The VMtree-OW is not tested as the NANDmemory does not support hardware overwriting, and the B-tree also doesnot run on the NAND memory, which does not support in-place writing onindividual pages. For the pair-wise comparisons in the figure, the percentdifference is calculated by ((tree1−tree2)/tree2). For the VMtreeSD (tree1)vs BtreeSD (tree2), this means VMtreeSD performs 2.2% more reads, 0.5%more writes, and takes 9.1% longer in time.The VMtree is slightly slower than the B-tree on the SD card due tosome additional I/Os and overhead due to virtual mappings and space man-agement. The VMtree on NAND outperforms both the B-tree and VMtreerunning on the SD card. It performs the same number of I/Os but executeson a chip with higher write bandwidth. These results demonstrate that theVMtree implementation can run on raw memory with very high efficiency.This is a significant benefit as the NAND chip cost of $2 to $4 is 5 timesless expensive than an SD card ($10 to $20) and easier to deploy on smalldevices as it is directly on the board.Figure 7.10 shows the insert bandwidth when adding logging. Since thePIC platform used page sizes of 2 KB, the number of log pages varies from 0to 3. Note that 1 log buffer for the PIC is equivalent to 4 log buffers on theother platform that used 512 byte pages. The addition of at least 1 log bufferallows for significant performance improvement. A log buffer of 2048 bytesincreased insert throughput by over 2 times for all B-tree implementations.The relative performance of the implementations with the same size logbuffer was consistent for all log buffer sizes.987.1. RANDOM DATA(a) B-tree(b) VMtree(c) VMtree-OWFigure 7.6: Insert Performance with Varying Number of Log Buffer on SDCard (ARM)997.1. RANDOM DATA(a) B-tree(b) VMtree(c) VMtree-OWFigure 7.7: Insert Performance With Varying Number of Log Buffers onDataflash (ARM)1007.1. RANDOM DATA(a) SD Card(b) DataflashFigure 7.8: Insert Throughput With Varying Number of Log Buffers (ARM)1017.1. RANDOM DATAFigure 7.9: Insert Performance on SD Card and NAND Memory (PIC)Figure 7.10: Relative Insert Bandwidth on NAND and SD Card With Vary-ing Number of Log Buffers (PIC)1027.2. SENSOR DATAThe query performance was within 5% for the B-tree and VMtree, withthe VMtree on NAND being slightly faster (1 to 4%) than the other twoconfigurations. The I/Os performed is the same in all cases, so it is notexpected to have a major performance difference.The results demonstrate the advantage of customizing B-tree implemen-tations for storage-specific properties. The addition of a log buffer may havesubstantial performance improvements while not requiring a lot of memory.7.2 Sensor DataTwo sensor data sets were evaluated. The environmental weather sta-tion data set used for evaluation of sensor indexing algorithms in [FOL21,ZYLK+05] contains 100,000 timestamp samples of temperature, precipita-tion, humidity, and wind speed on an hourly sample interval. The WESAD(wearable stress and affect detection) health data set [SRD+18] containssensor measurements including electrocardiogram (ECG), electrodermal ac-tivity, electromyogram, respiration, body temperature, and three-axis accel-eration for multiple patients. 500,000 samples from patient S7 were used.From both data sets, 10,000 records are used. The B-tree index stores8-byte index entries consisting of data value (i.e. temperature or ECG) andthe record id for retrieval in the timeseries data set. Note that although thedata is ordered by timestamp, it is not ordered by data value. Data valuesmay have considerable duplication and temporal clustering. The B-tree isfunctioning as a secondary index on the data value for use with rapid lookupon the measured data value. The buffer memory allocated was M=3 pagebuffers. The experiment inserted 10,000 records and then ran 10,000 querieson the B-tree.The insert throughput results on the 32-bit ARM processor for SD cardstorage and Dataflash are in Figure 7.11. The relative performance of theimplementations on the SD card is the same as the random data set withVMtree slightly slower than the B-tree. On Dataflash, VMtree-OW has afactor of 3 to 4 speedup over the B-tree. VMtree also is faster than theB-tree as its sequential write pattern over the pre-erased storage is moreefficient than the in-place erase-then-write done by the B-tree.A log buffer has even more dramatic performance improvement on sensordata compared to random data due to temporal clustering. The temperaturedata is slowly changing, and batching data inserts even with only a singlelog buffer reduces I/O and time by 63-72% for all B-tree variants. There isless relative improvement for VMtree-OW on Dataflash compared to the I/O1037.2. SENSOR DATA(a) SD Card(b) DataflashFigure 7.11: Insert Throughput Temperature Data (ARM)1047.3. OPTIMIZING MEMORY USAGEreduction as the algorithm is already very efficient with using its page-leveloverwrites.Further experiments were run indexing other environmental variables in-cluding humidity, pressure, and wind speed. Although the percentage I/Osavings using the log buffer varies depending on the amount of duplicationand temporal clustering of the data, all environmental variables demon-strated substantial savings when using the log buffer. This includes datasampled every minute compared to every hour. The relative performance ofthe B-tree variants was consistent regardless of data set and log buffer size.The health data displayed similar performance characteristics as shownin Figure 7.12. One log buffer is sufficient to achieve high performance.VMtree-OW has throughput between 3 and 5 times higher than the B-treeon Dataflash.There were no interesting query differences in any of the data sets andlog sizes as the number of I/Os were basically identical. There is no uniqueperformance differences compared to random data with VMtree-OW con-tinuing to be slightly slower due to its linear search within a node.On the 16-bit PIC platform, the results are consistent with the faster32-bit ARM platform. The insert throughput on the SD card is shown forthe temperature and health data sets in Figure 7.13. Addition of one logbuffer results in a factor of 9 throughput improvement for the temperaturedata and 5 times for the health data. VMtree on NAND consistently hasthe highest performance.7.3 Optimizing Memory UsageGiven the very low RAM, a key optimization is determining the appro-priate way to use any additional RAM. For all B-tree variants, the minimumnumber of buffers is 3 to supporting reads, writes, and tree maintenance.There are two possibilities for allocating additional memory: general pagebuffers and the log buffer. General page buffers store in RAM pages usingan LRU buffer. The log buffer will buffer operations before performing themon the tree. Additional pages in the log buffer allows for batching a largernumber of operations before modifying the tree.Experiments were conducted using the random data set and temperaturedata set varying the number of page buffers used from 3 to 10 and comparingthat with using a log buffer with 0 pages or 1 page. The results are shownin Figures 7.14 and 7.15 for write and read throughput.For write throughput, adding additional page buffers when there is no1057.3. OPTIMIZING MEMORY USAGE(a) SD Card(b) DataflashFigure 7.12: Insert Throughput Health Data (ARM)1067.3. OPTIMIZING MEMORY USAGE(a) Temperature Data(b) Health DataFigure 7.13: Insert Throughput Temperature and Health Data (PIC)1077.3. OPTIMIZING MEMORY USAGE(a) Random Data(b) Temperature DataFigure 7.14: Write Throughput With Varying Memory (ARM)1087.3. OPTIMIZING MEMORY USAGE(a) Random Data(b) Temperature DataFigure 7.15: Read Throughput With Varying Memory (ARM)1097.4. VARYING DATA SIZElog buffer increases throughput for the B-tree by 5 to 25% for random dataand less than 5% for temperature data. The buffer hit rate for temperaturedata is quite high and does not improve substantially with more buffers.The VMtree is similar except performance improvement for random data islower between 3 to 14% due to lower buffer hit rate. Adding more buffersdoes not change the write I/Os but reduces reads due to more buffer hits.Adding a log buffer has a much larger effect for both the random andtemperature data with a very significant increase for the temperature datadue to clustering. Going from three to four page buffers allows the system tobuffer in memory a complete working path from root to leaf, which avoidshaving to re-read interior nodes on the path to the leaf when performingsplits and tree maintenance.Read throughput is not affected by a log buffer. Adding page buffersimproves read performance by increasing the buffer hit rate. This is es-pecially noticeable with data with high duplication and clustering like thetemperature data.When utilizing a log buffer to delay and batch updates is feasible for theapplication use case, there is a more significant benefit in dedicating memoryto the log buffer compared to general page buffers. Adding sufficient generalpage buffers to buffer a root-to-leaf path is also valuable.7.4 Varying Data SizeThe VMtree uses more memory than the B-tree and VMtree-OW tomaintain its virtual mapping table and free space bitmap. The VMtree alsomust perform garbage collection when it wraps around in the storage spaceby moving valid pages before erasing blocks. To quantify these impacts,100,000 records of random and temperature data was tested. Testing on theSD card allows comparisons with B-tree, which does not run on raw NAND.The storage space was set at 5000 pages, M=4 for page buffers, andthe mapping table of 4096 bytes. This results in VMtree having to wraparound in the storage space multiple times and manage the storage. For100,000 records, it performed over 135,000 writes requiring 27 passes throughstorage.The results are in Figure 7.16. For the random data, VMtree starts offwithin 1% of write throughput at 10,000 records. By 100,000 records, B-treehas a throughput 22% higher. The difference is primarily due to the virtualmapping table being near full resulting in more I/Os. For the temperaturedata set, the mapping table is only 20% full, and there is almost no difference1107.5. VARYING SD CARD HARDWAREin time and I/O between the algorithms. It is the additional I/Os relatedto collisions in the mapping table that result in slower performance muchmore than the garbage collection of storage. The slight downward trend inwrite throughput for both algorithms is due to the B-tree size going fromdepth 3 to 4 as the number of records increases.Similar to prior experiments, there is no significant difference in readperformance. Both variants scale well to larger data sizes. However, VMtreeis restricted on the maximum size of the tree due to its memory consumptionfor the free space bitmap. It degrades well for larger data sizes even whenthe mapping table is small.7.5 Varying SD Card HardwareSimilar to SSDs, SD card performance varies between manufacturers.The performance difference between VMtree and B-tree is impacted basedon the ratio of sequential versus random write throughput. VMtree performssequential writes, which may be higher performing than random writes doneby the B-tree, depending on the implementation of the file system API andSD card.Experiments on the 16 GB SD card, with a sequential-to-random writethroughput ratio of 2, did not show any significant performance differ-ences. Five additional SD cards from various manufacturers (Lexar, Sandisk,Kingston) were tested. The sequential-to-random write throughput variedbetween 1.5 and four times. The impact on VMtree compared to B-treewas less than 5%. Although older SD cards may have higher sequential-to-random write throughput ratios, the cards tested in the experiment envi-ronment did not show much difference. This may have been impacted bythe slow CPU and bus speed as sequential write performance on all cardswas limited by the bus speed not the SD card write speed.7.6 DiscussionThe experimental results demonstrate the different performance for theB-tree variants and the advantage of adapting to storage-specific properties.In general, the base B-tree implementation is the best choice for file-basedstorage where the algorithm does not have to interact with raw physicalstorage. The VMtree has competitive performance for certain data sizes,but its additional overhead for managing the storage has no benefit unless1117.6. DISCUSSION(a) Random Data(b) Temperature DataFigure 7.16: Write Throughput for Larger Data Sets (ARM)1127.6. DISCUSSIONthe storage has a significant difference in random versus sequential writeperformance.VMtree executes on raw NAND flash with high performance and usesonly 3 to 4 KB of memory. This allows B-trees to be used on small embeddeddevices where it was not previously possible. For devices that support pageovewriting, VMtree-OW has significant performance improvements, and un-like VMtree, does not need a virtual mapping table.The addition of log buffers to enable batch inserts has significant perfor-mance improvements, especially for sensor data. If the use case is tolerant ofdata loss of the buffered data, then adding log buffers has the most impactwhen more memory is available.113Chapter 8Conclusion8.1 SummarySmall embedded devices are key data collectors in applications such asInternet of Things and Cyber-Physical Systems. These devices are char-acterised by their limited resources including energy, computational power,storage and memory. Improving data processing and indexing performanceon these memory-constrained devices will reduce energy usage, minimizenetwork transmission, and improve latency and bandwidth. This work de-veloped, implemented, and experimentally evaluated multiple different in-dex structures (both sequential and random) optimized for different storagetypes running on various embedded devices.The implementation of a sequential index “SBITS” for indexing sequen-tial, time series timestamps on embedded devices required minimal spaceoverhead (<2%) and had insert performance within 10% of a sequential file.SBITS has 10 times the query performance with only a 10% reduction ininsert performance. This represents the best compromise between insertand queries for workloads with moderate query loads. SBITS was com-pared against sequential B-trees, sorted files, and hashing approaches anddemonstrated superior performance [FOL21, OKFL22]. SBITS is currentlythe highest-performing embedded sequential indexing technique for smallembedded devices. With append-only time series data and known querypatterns, SBITS minimizes I/Os and energy usage by building the minimalpossible index to support the required queries. Queries by timestamp re-quire only 1 read I/O, and data value queries will minimize data read if thebitmap index is tuned to match query predicates. The fundamental positiontaken is that the index structure can be adapted at design time, given thatthe queries to be supported will be known in advance. This approach allowsfor optimizing the index structure to efficiently handle the specific types ofqueries anticipated, thus improving performance and resource utilization.Although SBITS excels at indexing sorted, sequential data, there areoften use cases where the data is inserted randomly. To address this, theB+tree algorithm was adapted to use low memory on embedded devices1148.2. FUTURE WORKwith SD card storage. This adaptation allows the B+tree to efficientlyhandle random data insertions while maintaining a low memory footprint,making it suitable for resource-constrained environments. Furthermore, thiswork developed, implemented and experimentally evaluated several storage-adaptive B+tree implementations, called VMtree, capable of deploymenton a wide variety of storage devices including SD cards, NOR, and NANDflash memories. VMtree is capable of deployment on raw storage not previ-ously possible with other embedded indexes. VMtree implements a uniqueapproach to reducing write amplification for B-tree updates by using vir-tual mappings. Virtual mappings allow physical page movements withoutrebuilding the B-tree index structure.The other key optimization was the application of log buffering opera-tions as used in prior work on B-trees for servers. When possible for theapplication use case, log buffering has a dramatic benefit for many sensordata sets with an insert bandwidth 3 to 5 times faster. Optimizing formemory that supports page overwriting also results in a speedup of 4 times.Overall, the three different optimized implementations allow for deploymentacross a wide-range of devices and memory types and support efficient B-treeindexing while only requiring about 4 KB of memory.8.2 Future WorkThere are several promising research directions in the field of memory-constrained indexing.− The performance of value queries in SBITS is influenced by the se-lectivity of the query predicates and the ability to effectively capturethis selectivity within the bitmap index. If the bitmap index does notefficiently capture the selectivity, the query performance can degrade.Further work will look into methods of determining and tuning thequery predicates for SBITS.− Every index-based query in SBITS involves reading the entire index.For datasets with a large number of pages, the overhead of reading theindex can be significant. Future work can investigate scenarios wherethe entire index file does not need to be scanned to enable higherperformance.− The B+-tree and VMtree implementations did not use known B-treeoptimizations such as compression and key prefixes. Adapting these1158.2. FUTURE WORKtechniques to the embedded B-tree implementations would be inter-esting future work as the additional storage efficiency gained by com-pression must be balanced with the increased CPU costs.− As demonstrated in Chapter 7 (Figures 7.6 and 7.7), adding log buffersto enable batch inserts has significant performance improvements. Datacompression with the log buffers may allow for more records to bebuffered before they must be processed in batch.− Due to their byte-addressable nature, high density, and low read-/write latency, Persistent Memories (PM) such as Phase Change Mem-ory (PCM) [ZZYZ09], Resistive Random Access Memory (RRAM)[MWD+21], and Spin-transfer Torque Random Access Memory (STT-RAM) [MWD+21] have recently emerged as potential replacements forDRAM as main memory. Additionally, PMs are non-volatile, makingthem strong contenders for storage systems [Dir], effectively bridgingthe gap between database memory and storage. However, similar toflash memories, PMs present challenges to indexes such as B+tree dueto their asymmetric read/write characteristics and limited write en-durance. Further optimizations of these algorithms for PMs will bethe next step in designing storage-specific indexex.− SBITS has been deployed as the storage and index architecture forthe embedded database EmbedDB [SAL24b, SAL24a]. Experimentalresults demonstrate it outperforms SQLite for some time series dataprocessing even on larger devices such as a Raspberry Pi. Future workis to integrate the VMtree into EmbedDB and perform further queryand index optimization. Deploying this research work into EmbedDBmakes it accessible to embedded developers.All the experiments in this work were conducted on serial flash memo-ries using standard SPI communication. Future work will include runningthese experiments using flash memories with other faster protocols, such asquad SPI and parallel communication protocols. Investigating the possibledeployment of these algorithms on commercial key-value DBMSs such asBerkeley DB is also a promising direction for future research.116Bibliography[Ade24] Adesto Technologies. AT45DB641E 64-Mbit DataFlash.https://www.digikey.com/en/htmldatasheets/production/1376615/0/0/1/at45db641e-uun2b-t, 2024.→ pages 4, 85, 90, 93[AGBA19] Raja Appuswamy, Goetz Graefe, Renata Borovica-Gajic, andAnastasia Ailamaki. The five-minute rule 30 years later andits impact on the storage hierarchy. Communications of theACM, 62(11):114–120, 2019. → pages 2, 86[AGS+09] Devesh Agrawal, Deepak Ganesan, Ramesh Sitaraman, YanleiDiao, and Shashi Singh. Lazy-adaptive tree: An optimizedindex structure for flash devices. Proceedings of the VLDBEndowment, 2(1):361–372, 2009. → pages 25[ASSC02] Ian F Akyildiz, Weilian Su, Yogesh Sankarasubramaniam,and Erdal Cayirci. A survey on sensor networks. IEEE Com-munications magazine, 40(8):102–114, 2002. → pages 18[AVR] Avr® mcus — microchip technology. https://www.microchip.com/en-us/products/microcontrollers-and-microprocessors/8-bit-mcus/avr-mcus. (Accessed on 05/21/2024). → pages 8[BCDV09] Chiara Buratti, Andrea Conti, Davide Dardari, and RobertoVerdone. An overview on wireless sensor networks technologyand evolution. Sensors, 9(9):6869–6896, 2009. → pages 18[BCS92] R Bez, D Cantarelli, and S Serra. The channel hot electronprogramming of a floating gate mosfet: An analytical study.In 12th Nonvolatile Semiconductor Memory Workshop, Mon-terey, CA, 1992. → pages 9[BFJ+15] Michael A. Bender, Martin Farach-Colton, William Jannen,Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun117BibliographyYuan, and Yang Zhan. An Introduction to Bϵ-trees andWrite-Optimization. Usenix Mag., 40(5):22–28, 2015. → pages 2,50, 71, 84, 87[BHH07] Siwoo Byun, Moonhaeng Huh, and Hoyoung Hwang. Anindex rewriting scheme using compression for flash memorydatabase systems. Journal of information science, 33(4):398–415, 2007. → pages 21, 22[BM72] Rudolf Bayer and Edward M. McCreight. Organization andmaintenance of large ordered indices. Acta Informatica,1:173–189, 1972. → pages 82, 85[Buy] Buy a raspberry pi pico – raspberry pi. https://www.raspberrypi.com/products/raspberry-pi-pico/. (Ac-cessed on 05/21/2024). → pages 8[CES04] David Culler, Deborah Estrin, and Mani Srivastava. Guest ed-itors’ introduction: Overview of sensor networks. Computer,37(08):41–49, 2004. → pages 18[CLGM15] Yu Cai, Yixin Luo, Saugata Ghose, and Onur Mutlu. Readdisturb errors in mlc nand flash memory: Characterization,mitigation, and recovery. In 2015 45th Annual IEEE/IFIP In-ternational Conference on Dependable Systems and Networks,pages 438–449. IEEE, 2015. → pages 10[CMMS08] L Crippa, R Micheloni, I Motta, and M Sangalli. Nonvolatilememories: Nor vs. nand architectures. In Memories in Wire-less Systems, pages 29–53. Springer, 2008. → pages 9[Cod70] Edgar F Codd. A relational model of data for large shareddata banks. Communications of the ACM, 13(6):377–387,1970. → pages 5[Cof] Coffee — contiki-ng documentation. https://docs.contiki-ng.org/en/master/doc/programming/Coffee.html. (Accessed on 04/28/2024). → pages 20, 31[Com79] Douglas Comer. Ubiquitous B-Tree. ACM Computing Sur-veys, 11(2):121–137, Jun 1979. → pages 82118Bibliography[CPP+09] Tae-Sun Chung, Dong-Joo Park, Sangwon Park, Dong-HoLee, Sang-Won Lee, and Ha-Joo Song. A survey of flash trans-lation layer. Journal of Systems Architecture, 55(5):332 – 343,2009. → pages 3[Dir] Direct from development - intel optane dc persistent mem-ory module. https://downloads.dell.com/manuals/common/Direct_From_Development_-_Intel_Optane_DC_Persistent_Memory_Module.pdf. (Accessed on05/22/2024). → pages 116[DISK20] Diego Didona, Nikolas Ioannou, Radu Stoica, and Kornil-ios Kourtis. Toward a better understanding and evalua-tion of tree structures on flash SSDs. Proc. VLDB Endow.,14(3):364–377, nov 2020. → pages 84[DL14] Graeme Douglas and Ramon Lawrence. Littled: a sqldatabase for sensor nodes and embedded applications. InProceedings of the 29th Annual ACM Symposium on AppliedComputing, pages 827–832, 2014. → pages 20[DMLD10] Biplob Debnath, Mohamed F Mokbel, David J Lilja, andDavid Du. Deferred updates for flash-based storage. In 2010IEEE 26th Symposium on Mass Storage Systems and Tech-nologies (MSST), pages 1–6. IEEE, 2010. → pages 17[DS8] Ds8626 stm32f40xxx.book. https://www.st.com/resource/en/datasheet/stm32f405rg.pdf. (Accessedon 05/19/2024). → pages 19[eCo] ecos. http://ecos.sourceware.org/. (Accessed on04/28/2024). → pages 20[EM05] Jo¨rn Engel and Robert Mertens. Logfs-finally a scalable flashfile system. In 12th International Linux System TechnologyConference. Citeseer, 2005. → pages 21, 23[ESP] Esp8266 wi-fi soc — espressif systems. https://www.espressif.com/en/products/socs/esp8266. (Accessed on05/21/2024). → pages 8[eXta] extremedb. https://www.ecoscentric.com/middleware/extremedb.shtml. (Accessed on 04/28/2024). → pages 19119Bibliography[eXtb] extremedb database management system for professional de-velopers - mcobject llc. https://www.mcobject.com/. (Ac-cessed on 04/28/2024). → pages 19[FABM20] Athanasios Fevgas, Leonidas Akritidis, Panayiotis Bozanis,and Yannis Manolopoulos. Indexing in flash storage devices:a survey on challenges, current approaches, and future trends.VLDB Journal, 29(1):273–311, 2020. → pages 2, 3, 83, 84, 86[FHD+15] Scott Fazackerley, Eric Huang, Graeme Douglas, Raffi Kud-lac, and Ramon Lawrence. Key-value store implementationsfor Arduino microcontrollers. In IEEE 28th Canadian Confer-ence on Electrical and Computer Engineering, pages 158–164,2015. → pages 31[FL10] S. Fazackerley and R. Lawrence. Reducing turfgrass waterconsumption using sensor nodes and an adaptive irrigationcontroller. In 2010 IEEE Sensors Applications Symposium(SAS), pages 90–94, 2010. → pages 81[FL11] Scott Fazackerley and Ramon Lawrence. A flash residentfile system for embedded sensor networks. In 2011 24thCanadian Conference on Electrical and Computer Engineer-ing(CCECE), pages 001400–001405, 2011. → pages 42[FN28] Ralph Howard Fowler and Lothar Nordheim. Electron emis-sion in intense electric fields. Proceedings of the Royal Societyof London. Series A, Containing Papers of a Mathematicaland Physical Character, 119(781):173–181, 1928. → pages 9[FOKFL18] Matthew Fritter, Nadir Ould-Khessal, Scott Fazackerley, andRamon Lawrence. Experimental evaluation of hash functionperformance on embedded devices. In 2018 IEEE CanadianConference on Electrical & Computer Engineering (CCECE),pages 1–5. IEEE, 2018. → pages 33[FOL21] Scott Fazackerley, Nadir Ould-Khessal, and Ramon Lawrence.Efficient Flash Indexing for Time Series Data on Memory-constrained Embedded Sensor Devices. In Proceedings ofthe 10th International Conference on Sensor Networks, SEN-SORNETS 2021, pages 92–99. SCITEPRESS, 2021. → pages32, 33, 35, 54, 65, 85, 86, 103, 114120Bibliography[FOM+19] Andrew Feltham, Nadir Ould-Khessal, Spencer MacBeth,Scott Fazackerley, and Ramon Lawrence. Linear Hashing Im-plementations for Flash Memory. In 21st International Con-ference Enterprise Information Systems Selected Papers, vol-ume 378 of Lecture Notes in Business Information Processing,pages 386–405. Springer, 2019. → pages 29, 33, 46, 49[FPL16] S. Fazackerley, W. Penson, and R. Lawrence. Write improve-ment strategies for serial NOR dataflash memory. In 2016IEEE Canadian Conference on Electrical and Computer En-gineering (CCECE), pages 1–6, 2016. → pages 90[FV20] Paolo Ferragina and Giorgio Vinciguerra. The PGM-index: afully-dynamic compressed learned index with provable worst-case bounds. Proc. VLDB Endow., 13(8):1162–1175, 2020. →pages 57, 69[GKK12] Goetz Graefe, Hideaki Kimura, and Harumi A. Kuno. Fosterb-trees. ACM Transactions on Database Systems, 37(3):17:1–17:29, 2012. → pages 82, 84, 89[GR93] Jim Gray and Andreas Reuter. Transaction processing: con-cepts and techniques. Morgan Kaufmann, 1993. → pages 82[Gra04] Goetz Graefe. Write-Optimized B-Trees. In Proceedings ofthe Thirtieth International Conference on Very Large DataBases VLDB 2004, pages 672–683, 2004. → pages 82[Gra12] Goetz Graefe. A survey of B-tree logging and recovery tech-niques. ACM Transactions on Database Systems, 37(1):1:1–1:35, 2012. → pages 82[GT05] Eran Gal and Sivan Toledo. Algorithms and data struc-tures for flash memories. ACM Computing Surveys (CSUR),37(2):138–163, 2005. → pages 16[HKVP19] Sergey Hardock, Andreas Koch, Tobias Vinc¸on, and IliaPetrov. IPA-IDX: In-Place Appends for B-Tree Indices. In15th International Workshop on Data Management, pages18:1–18:3. ACM, 2019. → pages 51, 72, 84, 90[Int98] C Intel. Understanding the flash translation layer (ftl) speci-fication, 1998. → pages 15121Bibliography[ITT] Ittia db sql — ittia. https://www.ittia.com/products/ittia-db-sql. (Accessed on 04/28/2024). → pages 20[KJKK07] Dongwon Kang, Dawoon Jung, Jeong-Uk Kang, and Jin-SooKim. µ-tree: An ordered index structure for nand flash mem-ory. In Proceedings of the 7th ACM & IEEE internationalconference on Embedded software, pages 144–153, 2007. →pages 24[KL15] Bo-Kyeong Kim and Dong-Ho Lee. LSB-Tree: a log-structured B-Tree index structure for NAND flash SSDs. Des.Autom. Embed. Syst., 19(1-2):77–100, 2015. → pages 2, 46,51, 72, 84, 87[KMB13] Ju¨rgen Kaiser, Fabio Margaglia, and Andre´ Brinkmann. Ex-tending SSD lifetime in database applications with page over-writes. In 6th Annual International Systems and Storage Con-ference, pages 11:1–11:12. ACM, 2013. → pages 84[KWS10a] Yi-Reun Kim, Kyu-Young Whang, and Il-Yeol Song. Page-differential logging: an efficient and dbms-independent ap-proach for storing data into flash memory. SIGMOD ’10,page 363–374, New York, NY, USA, 2010. Association forComputing Machinery. → pages 17[KWS10b] Yi-Reun Kim, Kyu-Young Whang, and Il-Yeol Song. Page-differential logging: an efficient and DBMS-independent ap-proach for storing data into flash memory. In Proceedings ofthe 2010 ACM SIGMOD International Conference on Man-agement of data, pages 363–374, 2010. → pages 17[LAH03] Chang-Woo Lee, Kyoung-Hwan Ahn, and Bong-Hee Hong.A study of performance decision factor for moving objectdatabase in main memory index. In Proceedings of the KoreaInformation Processing Society Conference, pages 1575–1578.Korea Information Processing Society, 2003. → pages 14[Lar82a] Per-A˚ke Larson. Performance analysis of linear hashing withpartial expansions. ACM Transactions on Database Systems(TODS), 7(4):566–587, 1982. → pages 26122Bibliography[Lar82b] Per-A˚ke Larson. Performance analysis of linear hash-ing with partial expansions. ACM Trans. Database Syst.,7(4):566–587, dec 1982. → pages 26[Lee07] Edward A. Lee. Computing foundations and practice forcyber-physical systems: A preliminary report. Technical Re-port UCB/EECS-2007-72, May 2007. → pages 7[Lit80] Witold Litwin. Linear hashing: a new tool for file and tableaddressing. In VLDB, volume 80, pages 1–3, 1980. → pages26, 33[Liv] Live from earth and mars - grayskies - atmospheric scienceson earth. https://www-k12.atmos.washington.edu/k12/grayskies/. (Accessed on 05/22/2024). → pages 60[LKW+09] Ki Yong Lee, Hyojun Kim, Kyoung-Gu Woo, Yon DohnChung, and Myoung Ho Kim. Design and implementationof mlc nand flash-based dbms for mobile devices. Journal ofSystems and Software, 82(9):1447–1458, 2009. → pages 17[LLS13] Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta.The Bw-Tree: A B-tree for new hardware platforms. In2013 IEEE 29th International Conference on Data Engineer-ing (ICDE), pages 302–313, 2013. → pages 23, 82, 84, 87,88[LM07] Sang-Won Lee and Bongki Moon. Design of flash-based dbms:an in-page logging approach. In Proceedings of the 2007 ACMSIGMOD international conference on Management of data,pages 55–66, 2007. → pages 16, 17, 26[LPC] Lpc800 series: Low-cost microcontrollers (mcus)based on arm® cortex®-m0+ cores —nxp semiconductors. https://www.nxp.com/products/processors-and-microcontrollers/arm-microcontrollers/general-purpose-mcus/lpc800-arm-cortex-m0-plus-:MC_71785. (Accessedon 05/21/2024). → pages 8[LZYK+06] Song Lin, Demetrios Zeinalipour-Yazti, Vana Kalogeraki,Dimitrios Gunopulos, and Walid A Najjar. Efficient indexing123Bibliographydata structures for flash-based sensor devices. ACM Trans-actions on Storage (TOS), 2(4):468–503, 2006. → pages 21,30[Mic] Microcontrollers (mcus) — microchip technology.https://www.microchip.com/en-us/products/microcontrollers-and-microprocessors. (Accessedon 05/21/2024). → pages 8[MKvR+20] Ryan Marcus, Andreas Kipf, Alexander van Renen, MihailStoian, Sanchit Misra, Alfons Kemper, Thomas Neumann,and Tim Kraska. Benchmarking learned indexes. Proc. VLDBEndow., 14(1):1–13, 2020. → pages 57, 69[MWD+21] Rui-Xiang Ma, Fei Wu, Bu-Rong Dong, Meng Zhang, Wei-Jun Li, and Chang-Sheng Xie. Write-optimized b+ tree in-dex technology for persistent memory. Journal of ComputerScience and Technology, 36:1037–1050, 2021. → pages 116[NK07] Suman Nath and Aman Kansal. Flashdb: Dynamic self-tuning database for nand flash. In Proceedings of the 6thinternational conference on Information processing in sensornetworks, pages 410–419, 2007. → pages 22[NLM12] Gap-Joo Na, Sang-Won Lee, and Bongki Moon. DynamicIn-Page Logging for B-tree Index. IEEE Trans. Knowl. DataEng., 24(7):1231–1243, 2012. → pages 2, 51, 72, 84, 87[OCGO96] Patrick E. O’Neil, Edward Cheng, Dieter Gawlick, and Eliza-beth J. O’Neil. The Log-Structured Merge-Tree (LSM-Tree).Acta Informatica, 33(4):351–385, 1996. → pages 51, 72[OFL21] Nadir Ould-Khessal, Scott Fazackerley, and Ramon Lawrence.B-tree Implementation for Memory-Constrained EmbeddedSystems. In 19th Int’l Conf on Embedded Systems, Cyber-physical Systems, and Applications (ESCS). CSREA Press,2021. → pages 32, 34, 51, 53, 71[OKFL20] Nadir Ould-Khessal, Scott Fazackerley, and Ramon Lawrence.Performance evaluation of embedded time series indexes usingbitmaps, partitioning, and trees. In International Conferenceon Sensor Networks, pages 125–151. Springer, 2020. → pages2, 34124Bibliography[OKFL22] Nadir Ould-Khessal, Scott Fazackerley, and Ramon Lawrence.Performance Evaluation of Embedded Time Series IndexesUsing Bitmaps, Partitioning, and Trees. In Invited papers ofSENSORNETS 2021, volume 1674 of Sensor Networks, pages125–151, 2022. → pages 33, 35, 87, 114[Ora] Oracle berkeley db — oracle canada. https://www.oracle.com/ca-en/database/technologies/related/berkeleydb.html. (Accessed on 04/28/2024). →pages 19[Owe06] Michael Owens. The definitive guide to SQLite. Springer,2006. → pages 18[PMSSY96] K. Pollari-Malmi, E. Soisalon-Soininen, and T. Ylonen. Con-currency control in b-trees with batch updates. IEEE Trans-actions on Knowledge and Data Engineering, 8(6):975–984,1996. → pages 83, 97[RHB+90] John Rosenberg, Frans Henskens, Fred Brown, Ron Morrison,and David Munro. Stability in a persistent store based on alarge virtual memory. In Security and Persistence: Proceed-ings of the International Workshop on Computer Architec-tures to Support Security and Persistence of Information 8–11May 1990, Bremen, West Germany, pages 229–245. Springer,1990. → pages 82[RKLP14] Hongchan Roh, Sungho Kim, Daewook Lee, and SanghyunPark. AS B-tree: A Study of an Efficient B+-tree for SSDs.J. Inf. Sci. Eng., 30(1):85–106, 2014. → pages 2, 51, 72, 84,87[RO92] Mendel Rosenblum and John K Ousterhout. The design andimplementation of a log-structured file system. ACM Trans-actions on Computer Systems (TOCS), 10(1):26–52, 1992. →pages 15[Rod08] Ohad Rodeh. B-trees, shadowing, and clones. 3(4), feb 2008.→ pages 82[SAL24a] Justin Schoenit, Seth Akins, and Ramon Lawrence.EmbedDB: A High-Performance Database for Resource-Constrained Embedded Systems Too Small for SQLite. In125Bibliography39th ACM/SIGAPP Symposium on Applied Computing (SAC’24), pages 345–346. ACM, 2024. → pages 116[SAL24b] Justin Schoenit, Seth Akins, and Ramon Lawrence. Em-bedDB: A High-Performance Time Series Database for Em-bedded Systems. In 26th International Conference on En-terprise Information Systems (ICEIS), pages 240–249. SCI-PRESS, 2024. → pages 116[Sama] Samsung s3c2410a. https://www.keil.com/dd/chip/4252.htm. (Accessed on 05/19/2024). → pages 19[Samb] Samsung s3c44b0x. https://www.keil.com/dd/chip/3835.htm. (Accessed on 05/19/2024). → pages 19[SDO18] Omer Berat Sezer, Erdogan Dogdu, and Ahmet MuratOzbayoglu. Context-Aware Computing, Learning, and BigData in Internet of Things: A Survey. IEEE Internet ofThings Journal, 5(1):1–27, 2018. → pages 36[SHHA98] S. Satoh, G. Hemink, K. Hatakeyama, and S. Aritome. Stress-induced leakage current of tunnel oxide derived from flashmemory read-disturb characteristics. IEEE Transactions onElectron Devices, 45(2):482–486, 1998. → pages 10[SPI] Spi nor flash — renesas. https://www.renesas.com/us/en/products/memory-logic/non-volatile-memory/spi-nor-flash. (Accessed on 05/22/2024). → pages 60[sql] SQLite Download Page — sqlite.org. https://www.sqlite.org/download.html. [Accessed 29-04-2024]. → pages 18[SRD+18] Philip Schmidt, Attila Reiss, Robert Duerichen, Claus Mar-berger, and Kristof Van Laerhoven. Introducing WESAD, aMultimodal Dataset for Wearable Stress and Affect Detection.In Proceedings of the 20th ACM International Conference onMultimodal Interaction, ICMI ’18, page 400–408. ACM, 2018.→ pages 96, 103[STM] Stm32f0 - arm cortex-m0 - usb microcontrollers- stmicroelectronics. https://www.st.com/en/microcontrollers-microprocessors/stm32f0-series.html. (Accessed on 05/21/2024). → pages 8126Bibliography[SWW+08] R. R. Sinha, M. Winslett, K. Wu, K. Stockinger, andA. Shoshani. Adaptive Bitmap Indexes for Space-ConstrainedSystems. In 2008 IEEE 24th International Conference onData Engineering, pages 1418–1420. IEEE, 2008. → pages 54[TD11a] Nicolas Tsiftes and Adam Dunkels. A database in every sen-sor. Proceedings of the 9th ACM Conference on EmbeddedNetworked Sensor Systems - SenSys ’11, page 316, 2011. →pages 20, 31[TD11b] Nicolas Tsiftes and Adam Dunkels. A database in every sen-sor. In Proceedings of the 9th ACM Conference on EmbeddedNetworked Sensor Systems, SenSys ’11, page 316–332. ACM,2011. → pages 31, 46, 84, 86[VCDSdM03] Marcos Augusto M Vieira, Claudionor N Coelho,DC Da Silva, and Jose´ Monteiro da Mata. Survey onwireless sensor network devices. In EFTA 2003. 2003IEEE Conference on Emerging Technologies and FactoryAutomation. Proceedings (Cat. No. 03TH8696), volume 1,pages 537–544. IEEE, 2003. → pages 18[WCK04] Chin-Hsien Wu, Li-Pin Chang, and Tei-Wei Kuo. An effi-cient b-tree layer for flash-memory storage systems. In Real-Time and Embedded Computing Systems and Applications:9th International Conference, RTCSA 2003, Tainan City,Taiwan, February 18-20, 2003. Revised Papers, pages 409–430. Springer, 2004. → pages 21[WKC07a] Chin-Hsien Wu, Tei-Wei Kuo, and Li-Ping Chang. An effi-cient B-tree layer implementation for flash-memory storagesystems. ACM Trans. Embed. Comput. Syst., 6(3):19, 2007.→ pages 2, 51, 72, 84, 87[WKC07b] Chin-Hsien Wu, Tei-Wei Kuo, and Li Ping Chang. An ef-ficient b-tree layer implementation for flash-memory storagesystems. ACM Transactions on Embedded Computing Sys-tems (TECS), 6(3):19–es, 2007. → pages 21[Woo01] David Woodhouse. Jffs: The journalling flash file system.In Ottawa linux symposium, volume 2001. Citeseer, 2001. →pages 15127Bibliography[WOS06] Kesheng Wu, Ekow J. Otoo, and Arie Shoshani. OptimizingBitmap Indices with Efficient Compression. ACM Transac-tions on Database Systems, 31(1):1–38, March 2006. → pages54[WPL+18] Ziqi Wang, Andrew Pavlo, Hyeontaek Lim, Viktor Leis,Huanchen Zhang, Michael Kaminsky, and David G. Ander-sen. Building a Bw-Tree Takes More Than Just Buzz Words.In Proceedings of the 2018 International Conference on Man-agement of Data, page 473–488. ACM, 2018. → pages 23, 82,84, 87, 88[WSS08] Kesheng Wu, Arie Shoshani, and Kurt Stockinger. Analysesof Multi-Level and Multi-Component Compressed Bitmap In-dexes. ACM Transactions on Database Systems, 35(1), Febru-ary 2008. → pages 54[YP12a] Shaoyi Yin and Philippe Pucheral. Pbfilter: A flash-basedindexing scheme for embedded systems. Information Systems,37(7):634–653, 2012. → pages 17[YP12b] Shaoyi Yin and Philippe Pucheral. PBFilter: A flash-basedindexing scheme for embedded systems. Information Systems,37(7):634 – 653, 2012. → pages 54, 84, 86[ZLL+20] Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G. An-dersen, Michael Kaminsky, Kimberly Keeton, and AndrewPavlo. Succinct range filters. ACM Transactions on DatabaseSystems, 45(2):5:1–5:31, 2020. → pages 54[ZYLK+05] Demetrios Zeinalipour-Yazti, Song Lin, Vana Kalogeraki,Dimitrios Gunopulos, and Walid Najjar. MicroHash: An Ef-ficient Index Structure for Flash-Based Sensor Devices. InProceedings of the FAST ’05 Conference on File and Stor-age Technologies, pages 31–43. USENIX Association, Dec 13,2005. → pages 37, 47, 60, 62, 67, 84, 86, 96, 103[ZZYZ09] Ping Zhou, Bo Zhao, Jun Yang, and Youtao Zhang. A durableand energy efficient main memory using phase change mem-ory technology. ACM SIGARCH computer architecture news,37(3):14–23, 2009. → pages 116128
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Lawrence, Ramon
Indexing on memory-constrained embedded devices
Text