#b-trees

Diferencias entre MySQL y MariaDB. Al mencionar MySQL y MariaDB, hablamos de los sistemas de gestión de bases de datos más usados a nivel mundial. La competencia es sana siempre que sea constructiva, pero no siempre fue así, o tal vez si, lo explicamos un poco. Ulf Michael Widenius (conocido como Monty), lanzó en 1996 junto a otros colaboradores la primera versión de MySQL. Hablamos del primer sistema de gestión de bases de datos de código abierto, puedes imaginar que supuso un bombazo con rotundo éxito a nivel mundial. Poco tardaron en llover las ofertas de compra, pero en MySQL imponen sus condiciones. En 2008 MySQL se formaliza su venta a Sun Microsystems (1.000 millones de dólares), pero se obliga a Sun a comprometerse sobre la comercialización de MySQL, siempre será open source. Además, Monty y su equipo pasarán a formar parte de Sun Microsystem como responsables del desarrollo del sistema de gestión de bases de datos. Estamos en 2008. Poco duró la feliz alianza, muy poco. Apenas unos meses después, en enero de 2009, el gigante Oracle Corporation se hace con Sun Microsystem a cambio de 5.750 millones de dólares, al día siguiente Monty y su equipo de desarrolladores se marchan para montar su propia empresa. Ríos de tinta se han escrito sobre el porqué se marcharon de la nueva adquisición de Oracle, yo creo que es evidente. Oracle Corporation pagó un sobrecoste del 42% por acción del valor real, algo realmente sospechoso e inusual. El nuevo propietario tampoco quiso comprometerse sobre MySQL como 100% open, a la vista lo tenemos ya que actualmente las versiones mejoradas de MySQL tienen un alto coste. Mi opinión personal: Oracle no solo se quitó de un plumazo una competencia real, sino que se quedó con los desarrollos del sistema de gestión de bases de datos orientados a internet (sitios web). Poco después de la adquisición, Oracle lanzó la nueva versión de su base de datos Oracle con propiedades integradas específicas para sitios web. En la siguiente agregaron más de 400 funciones nuevas, que como denunció publicamente Ulf Michael provenían de MySQL y sus proyectos futuros. Monty y su equipo de desarrolladores crean una nueva empresa, y nace MariaDB, una bifurcación de MySQL de alto rendimiento en la que confían la gran mayoría de distribuciones linux actuales. Los creadores originales de MySQL expusieron sus motivos del porqué nace MariaDB. Los principales creadores de MySQL deben permanecer juntos, es la única forma posible de mantener un sistema de gestión de bases de datos, excelente. Fomentar la continuidad del desarrollo por parte de la comunidad. Garantizar que siempre esté disponible MySQL de forma gratuita. Una vez conocemos un poco de la historia de MySQL, vemos sus principales diferencias.  

Diferencias entre MySQL y MariaDB

Quien usa MariaDB y MySQL Vemos algunos de los principales clientes de los dos sistemas de bases de datos. MariaDB Grandes corporaciones y los gigantes de linux utilizan MariaDB, podemos señalar las más conocidas: Google, Craigslist, Wikipedia, archlinux, RedHat, CentOS, Fedora, Suse, Ubuntu, AWS, 1and1, BlaBlaCart, Nokia, Samsung, y muchos más. MySQL Muchas de las grandes empresas que usan MySQL, no tienen fácil su migración a otro sistema. La lista es larga: GitHub, US Navy, NASA, Tesla, Netflix, WeChat, Facebook, Zendesk, Twitter, Zappos, YouTube, Spotify, y muchos más.   Compatibilidad entre MySQL y MariaDB MySQL: MySQL es un sistema de gestión de bases de datos relacionales (RDBMS). Al igual que otros sistema similares usa tablas, restricciones, disparadores, roles, procedimientos almacenados y vistas como componentes centrales de trabajo. Cada tabla se compone de filas, y cada fila contiene un mismo conjunto de columnas. MySQL utiliza claves primarias para identificar cada fila (llamado registro) de la tabla, y claves externas para verificar la integridad referencial de dos tablas relacionadas. MariaDB: Como MariaDB es una bifurcación de MySQL, la estructura de la base de datos y los índices son los mismos. Esto permite migrar de MySQL a MariaDB sin tener que modificar nuestras aplicaciones, los datos y estructuras serán los mismos. La conclusión es: Los archivos de configuración de datos y las tablas son compatibles. Las estructuras, protocolos y las API de cliente son las mismas. Los conectores MySQL también trabajan con MariaDB. El equipo de desarrollo de MariaDB intenta mantener una compatibilidad directa, mensualmente se compara y combina el código MariaDB con el código MySQL. Incluso la mayoría de comandos son los mismos, como mysqldump o mysqladmin.Aun así, existen diferencias entre MariaDB y MySQL que podrían llegar a causar problemas de compatibilidad mínimos. La migración de MySQL a MariaDB por parte de potencias empresariales como, Samsung o Google, no sentó nada bien en el seno de Oracle. Ahora mismo intentan diferenciarse de forma gradual, y un buen ejemplo lo encontramos en el diccionario de datos internos que se desarrolló para MySQL 8, que altera la forma en que los metadatos se guardan y utilizan. MariaDB no tiene esa función, y esto puede ser el principio del fin de la compatibilidad a nivel de archivo de datos entre MySQL y MariaDB.

B.Tech Back Paper Tuition For Design and Analysis of Algorithm

B.Tech Back Paper Tuition For Design and Analysis of Algorithm

Introduction: Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth of Functions, Performance Measurements, Sorting and Order Statistics – Shell Sort, Quick Sort, Merge Sort, Heap Sort, Comparison of Sorting Algorithms, Sorting in Linear Time. Advanced Data Structures: Red-Black Trees, B – Trees, Binomial Heaps, Fibonacci

B.Tech Back Paper Tuition In Greater Noida For Data Structure and Algorithms

B.Tech Back Paper Tuition In Greater Noida For Data Structure and Algorithms

Are you struggling with Back paper related to B.Tech Degree Course? We at CFA Engineering Academy help to to make it clear. We have highly qualified faculties who work with the students at zero level. We understand the needs of students. Weather you are a students of Amity University, AKTU University, Galgotias…

Type "the" into Google. Google searches 9 billion pages in .29 seconds. How does it do that? Try "chocolate". 197 million pages in .48 seconds. (No wonder we hate when the microwave takes 2 mins to boil water!)

When we search Google, we are searching an index of the data, not the data itself. We need a data structure that can store billions of keys and return a value in response to a query almost instantaneously. The answer: B-Trees.

B-Trees are a self-balancing tree where each node can have many children. If a node stores up to M keys, then it has M + 1 children. Suppose a tree stores 60 billion keys with nodes that store up to 1000 keys. To find a given key, the number of nodes searched  is <= 4. WAT? 

The reason is that the tree is very flat. The number of keys in a node ranges from M/2 to M (except for the root which has 2 keys). In 1979 (hey, B-Trees are not new), a theorist named Yao proved that, for random keys, the amount of empty space is about 44%. In the worse case, the height of the tree is (log base M/2) N. So, for M = 1000 and N = 62 billion, the height is 4.

But how can I search a B-tree with 62 billion keys? I can't fit it in memory. All the programs I write use some data structure that fits into memory and I don't even think about it.

One answer is virtual memory. If your machine has a MMU (Memory Management Unit) then you as a programmer can ignore details about what is in memory and what is on external storage. The MMU maps physical hardware addresses, wherever they are, to addresses that appear to be contiguous, in-memory addresses.

A more basic concept is that the program only needs to bring into memory the chunk of data that it needs to access. It only needs to access the nodes that it hits along the search path of the B-tree. So if the search, starting at the root, takes the left link, then the middle link, then the right link, before it hits a leaf node, then the program only needs to read in the those 3 nodes plus the leaf node. The program then searches for the value associated with the query key in the leaf node.

To explore B-trees and build one of my own, I decided to index the web pages that I can reach from www.princeton.edu  - and to explicitly read and write each of the nodes to/from disk. Each node stores 1000 keys. A key is a word on a web page. The value associated with the key is the set of urls on which the word is found. I limit the number of nodes in the tree to 200. (My goal is to get up to 1000 but first I have to deal with broken links and connection errors.)

As I type this, I can see the program in action. The tree starts as 1 node: the root. When it fills up to 1000, it splits into 2 nodes of 500 keys each (left and right). A new root is created that stores 2 keys: 1 key links to the left node and 1 to the right node. Every time a new root is created the tree height grows by 1.

After a node splits, I write each node to its own file on disk. After a search or insert completes, the only node in memory is the root. All other nodes in the search path are written to disk. When a new search or insert begins, only the files associated with the nodes in the search path are opened. By looking at the directory with the files, I can see them being updated (keys added to it) and new files created (nodes splitting). Watching the tree grow in real time is cool.

In the process of building an index of web pages and then searching for search terms in the index (271 urls from princeton homepage, 31 tree nodes, 20180 unique words, <2 avg node hits for each search - the tree has height = 1!), I learned more python along the way:

used python 3, requests, and BeautifulSoup to scrape the web pages for urls and words. Detours: unicode, Ned Batchelder's pycon video on unicode , json and pickle (and their differences), file modes (text and byte) and what these mean in python 3.

And yeah... using a python IDE is a new world. The ability to stop a program and navigate down a tree by expanding its nodes almost makes debugging fun.